Grouping associative array keys - in the same order

I have the following 2 arrays and would like to combine them. I'm more interested in the keys than their values. I'd like to take this

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

and turn it into something like this

$arr = array(
  'tom',
  'sally',     //unique from arr1, ended up here because she's before larry
  'drummer',   //开发者_Python百科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
);

The trick is I need to insert anything that's unique in the right spot/order based on what's before/after it. Thanks

---

Generally what you want is a non-trivial algorithm. It's called sequence matching or the longest common subsequence problem. I don't think there is a built-in PHP function to calculate that. Once you have the matches, you can process the unmatched items between them. Just note that there can be multiple common subsequences, so it will not be always possible for all items to be in the same order as in the original arrays, if you really want this kind of merging.

If don't need the best possible result, you could try an approximation like this, which is greedily looking for matches within 4 next items:

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