Группировка ассоциативных ключей массива - в том же порядке

Question

У меня есть следующие 2 массива и вы хотите их комбинировать. Меня больше интересуют ключи, чем их ценности. Я хотел бы воспользоваться этим

$arr1 = array(
    'tom' => "1", 
    'sally' => "20" // unique 
    'larry' => "2", 
    'kate' => "3", 
    'dave' => "23" //unique 
); 

$arr2 = array(
    'tom' => "11", 
    'larry' => "12", 
    'drummer' => "2", // unique 
    'kate' => "7", 
    'nick' => "3"  //unique 
); 

и превратить его в нечто вроде этого

$arr = array(
    'tom', 
    'sally',  //unique from arr1, ended up here because she's before larry 
    'drummer', //unique from arr2, ended up here because he's after larry 
    'larry', 
    'kate', 
    'dave',  //unique from arr1, ended up here because he's after the last 2 similar 
    'nick'  //unique from arr2, ended up here because he's after the last 2 similar 
); 

Хитрости мне нужно вставить что-нибудь, что это уникально в правильном месте/порядка, основанные на том, что до/после Это. Thanks

Answer 1

Как правило, вам нужен нетривиальный алгоритм. Это называется согласованием последовательностей или longest common subsequence problem. Я не думаю, что для его вычисления есть встроенная функция PHP. Когда у вас есть совпадения, вы можете обрабатывать непревзойденные элементы между ними. Просто обратите внимание, что может быть несколько общих подпоследовательностей, поэтому не всегда возможно, чтобы все элементы находились в том же порядке, что и в исходных массивах, если вы действительно хотите такого рода слияния.

Если не нужен наилучший результат, можно попробовать приближение, как это, который жадно ищет спички в течение 4 следующих пунктов:

$result = array(); 

$i = 0; 
$j = 0; 
while ($i < count($arr1)) { 
    // Look for a matching item in the next four items of $arr2 
    $k = 0; 
    while ($k < 4) { 
     // Do we have a match? 
     if ($arr1[$i] == $arr2[$j+$k]) { 
      // Add items from $arr2 that are before the matching item 
      while ($k-- > 0) { 
       $result[] = $arr2[$j]; 
       $j++; 
      } 
      $j++; 
      break; 
     } 
     $k++; 
    } 
    // Add the current item fro $arr1 
    $result[] = $arr1[$i]; 
    $i++; 
} 
// Add the remaining items from $arr2 
while ($j < count($arr2)) { 
    $result[] = $arr2[$j]; 
    $j++; 
} 

$result = array_unique($result);