How to check whether one array is a correctly ordered subset of another

Question

I have a few arrays of strings like:

$big = ['html', 'body', 'div', 'table', 'tbody', 'tr', 'td'];
$small = ['body', 'div', 'td'];
$wrong = ['td', 'body', 'div'];

I need to check whether $small and $wrong are to be found in $big. However I need the order to be the same. So my function should return true for $small and false for $wrong. It should be fairly trivial to do it manually but I need the code to be fast. So ideally if there is a built in that achieves this I would rather use that.

So the question is mainly whether such a built in exists. Here is the code I have come up with in case it doesn't:

/**
 * Returns whether the substack is contained in the stack in the correct order.  
 * 
 * @param string[] $stack           The substack to check
 * @param string[] $subStack        The substack to check 
 * @return bool
 */
function stackInStack(array $stack, array $subStack)
{

    // First let's do a simple array diff to save time on an ordered diff;
    // TODO: Check if this actually improves average performance.
    if (count(array_diff($subStack, $stack)) !== 0) return false;

    $stackSize = count($stack);
    $subStackSize = count($subStack);

    $stackIndex = 0;
    for ($subIndex = 0; $subIndex < $subStackSize; $subIndex++) {

        while (
            $stackIndex < $stackSize &&
            $stack[$stackIndex] !== $subStack[$subIndex]
        ) {
            $stackIndex++;
        }

        if ($stackIndex == $stackSize) {
            if ($subIndex <= $subStackSize - 1) {
                return false;
            } elseif ($subIndex > $subStackSize - 1) {
                throw new Exception('Very Strange Exception: subIndex has outgrown subStacksize');
            }
        } elseif ($stackIndex > $stackSize) {
            throw new Exception('Very Strange Exception: index has outgrown stacksize');
            break;
        } 

    }
    return true;
}

Provided a built in doesn't exist or is slow, any tips to improve the efficiency of the above code (other than to rewrite it in c) would also be greatly appreciated.

Answer 1

Assuming your arrays are not too big, you could use string comparisons instead. Something like this:

<?php

    $big = ['html', 'body', 'div', 'table', 'tbody', 'tr', 'td'];
    //$small = ['body', 'div', 'td']; // This is the original
    $small = ['body', 'div', 'table']; // This is for testing
    $wrong = ['td', 'body', 'div'];

    $bigToken = implode($big, ''); // Output: htmlbodydivtabletbodytrtd
    $smallToken = implode($small, ''); // Output: bodydivtable
    $wrongToken = implode($wrong, ''); // Output: tdbodydiv

    if (stristr($bigToken, $smallToken) !== false) {
        echo("Small is in big!");
    }
    elseif (stristr($bigToken, $wrongToken) !== false) {
        echo("Wrong is in big!");   
    }
    else {
        echo("No match found :)");
    }

?>

It basically converts the array to a string and checks if another string is contained inside. Performance wise, that will all depend on how large your actual arrays are, but this ensures the proper order and is easier to maintain.

---

As pointed out in the comments below, it would be a good idea to implode with some sort of token to ensure you are correctly separating the tags in instances where there may be a conflict.

Answer 2

This is a bit shorter than your version, it uses array_intersect() to work out the common elements in the two arrays and then compares the result with the sub stack to see if they are the same...

$big = ['html', 'body', 'div', 'table', 'tbody', 'tr', 'td'];
$small = ['body', 'div', 'td'];
$wrong = ['td', 'body', 'div'];

function stackInStack(array $stack, array $subStack)
{
    return array_values(array_intersect($stack, $subStack)) == $subStack;
}

var_dump(stackInStack($big, $small));
var_dump(stackInStack($big, $wrong));

Just to show what I mean

print_r(array_intersect($big, $wrong));

gives...

Array
(
    [1] => body
    [2] => div
    [6] => td
)

so compare this against $wrong and it isn't in the same order.

Answer 3

This is pretty much a duplicate of Nigel Ren's, but I had typed it up in another window.

Compute the intersection which will be in the order of the first array, re-index both and compare the intersection with the original:

$result = array_values(array_intersect($big, $small)) === array_values($small);
// true

$result = array_values(array_intersect($big, $wrong)) === array_values($wrong);
// false

Answer 4

Just use simple pointer to iterate over $needle which is the smaller array to be found as a subsequence in a bigger array. Once match is found, increment the pointer, else keep moving. If the pointer reaches the length of the smaller array, bingo, it's a subsequence, else it isn't.

Snippet:

<?php

$big = ['html', 'body', 'div', 'body','table', 'tbody', 'tr', 'td'];
$small = ['body', 'div', 'td'];
$wrong = ['td', 'body', 'div'];


function isSubsequence($haystack,$needle){
    if(count($needle) > count($haystack)) return false;
    $keys = array_keys($needle);
    $ptr = 0;
    $len = count($needle);

    foreach($haystack as $element){
        if($ptr === $len) return true;
        if($needle[$keys[$ptr]] === $element) $ptr++;
    }

    return $ptr === $len;
}


var_dump(isSubsequence($big, $small));
var_dump(isSubsequence($big, $wrong));

Demo: https://3v4l.org/vqBMj

Answer 5

this should work also on associative arrays:

"array_search()" will return the key corresponding to the value, so u can see if the sequence is right...

function is_array_in_array($array, $inarray){
    $pos = -1; $match = 0;
    $array = array_values($array);
    $inarray = array_values($inarray);
    foreach($array as $v){
        $p = array_search($v, $inarray);
        if($p===false || $p<=$pos) return false;
        $pos = $p; $match++;
    }
    if(count($array)==$match) return true;
    return false;
}

And it will return:

$small_assoc = array('A'=>'body', 'B'=>'div', 'C'=>'td');

is_array_in_array($small, $big);  # =1
is_array_in_array($wrong, $big);  # =0
is_array_in_array($big, $big);    # =1
is_array_in_array($small_assoc, $big); # =1