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

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
);

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

Answer 1

Как правило, вам нужен нетривиальный алгоритм. Это называется согласованием последовательности или самой длинной общей подпоследовательностью . Я не думаю, что есть встроенная функция 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);