如何检查一个数组是否是另一个数组的正确排序子集

Question

我有一些字符串数组，例如：

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

我需要检查 $small 和 $wrong 是否可以在 $big 中找到。但是我需要顺序相同。所以我的函数应该 return true $small 和 false $wrong。手动完成应该是相当简单的，但我需要代码要快。所以理想情况下，如果有内置功能可以实现这一点，我宁愿使用它。

所以问题主要是这样的内置是否存在。这是我想出的代码，以防万一：

/**
 * 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;
}

如果内置函数不存在或速度很慢，任何提高上述代码效率的技巧（除了用 c 重写它）也将不胜感激。

Answer 1

假设您的数组不是太大，您可以改用字符串比较。像这样：

<?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 :)");
    }

?>

它基本上是将数组转换为字符串并检查其中是否包含另一个字符串。性能方面，这完全取决于您的实际阵列有多大，但这确保了正确的顺序并且更容易维护。

正如下面的评论所指出的，implode 使用某种标记以确保在可能存在冲突的情况下正确分隔标签是个好主意。

Answer 2

这个比你的版本短了一点，它使用array_intersect()计算出两个数组中的共同元素，然后将结果与子堆栈进行比较，看它们是否相同...

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

只是为了说明我的意思

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

给...

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

因此将其与 $wrong 进行比较，发现顺序不同。

Answer 3

这几乎是 Nigel Ren's 的副本，但我在另一个 window 中输入了它。

计算第一个数组顺序的交集，重新索引两者并将交集与原始交集进行比较：

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

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

Answer 4

只需使用简单的指针来遍历 $needle，这是在更大的数组中作为子序列找到的更小的数组。一旦找到匹配项，增加指针，否则继续移动。如果指针到达较小数组的长度，bingo，它是一个子序列，否则不是。

片段：

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

演示： https://3v4l.org/vqBMj

Answer 5

这也适用于关联数组：

"array_search()"将return键对应的值，所以你可以看看顺序是否正确...

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

它会 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

如何检查一个数组是否是另一个数组的正确排序子集

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

php

arrays

optimization

php-7