php - 在 PHP 中优化从数组生成对数组而不重复

Question

我正在从一维数组生成大量对，代码必须严格检查并消除所有重复项(即，如果 [1,2] 存在，则不会生成 [2,1])。例如:

arr = [1,2,3]
pairs = [[1,2],[1,3],[2,3]]

我的解决方案目前需要 60 秒来生成大小为 N=460 的数组(结果将约为 110,000 对)。代码如下:

private function generateAllCombination($scripts)
{
    $combinations = [];
    $pairsIndex = '';

    for ($i = 0; $i < count($scripts) - 1; $i++) {
        for ($j = 0; $j < count($scripts); $j++) {
            // pairs must consist of tuples with distinct values
            if ($i != $j) {
                $pair = array(
                    $scripts[$i],
                    $scripts[$j]
                );

                // only add unique tuples
                $pairTuple = '[' . $i . ',' . $j. ']';
                $pairTupleRev = '[' . $j . ',' . $i . ']';

                if (strpos($pairsIndex, $pairTuple) === false) {
                    $combinations[] = $pair;

                    if ($j > $i) {
                        $pairsIndex .= $pairTupleRev;
                    }
                }
                else {
                    $pairsIndex = str_replace($pairTuple, '', $pairsIndex);
                }
            }
        }
    }

    return $combinations;
}

我认为检查重复项会在 2D 嵌套循环中杀死它，但不确定如何有效地优化它。任何建议将不胜感激。

Answer 1

如果 arr 不包含重复项，那么您只需从下一个索引开始第二个循环:

for ($i = 0; $i < count($scripts) - 1; $i++) {
      for ($j = $i + 1; $j < count($scripts); $j++) {
            //no need to check, just make a pair