PHP中数组中唯一排列的缓慢处理[关闭]

Question

嗨我试图获得PHP 7中的字符串列表的唯一排列，但发现它与较大的列表真的很慢。从理论上讲，物品清单可以很容易地扩展到15。

 //runs quickly returns more results
 function listPermutations($items, $perms = array()) {

    if (empty($items)) {
        $this->final[] = $perms;

    } else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
            $newitems = $items;
            $newperms = $perms;
            list($foo) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $foo);
            $this->listPermutations($newitems, $newperms);
        }
    }

    return $this->final;
}

//runs really slow, removed duplicate list orderings
function listUniquePermutations($items, $perms = array()) {

    if (empty($items)) {
        //this is much faster than if(!in_array($perms, $this->final))
        if(!in_array(join('-', $perms), $this->existing)) {
            $this->existing[] = join('-', $perms);
            $this->final[] = $perms;
        }

    } else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
            $newitems = $items;
            $newperms = $perms;
            list($foo) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $foo);
            $this->listUniquePermutations($newitems, $newperms);
        }
    }

    return $this->final;
}

好的，所以第一种方法很快，但后来我运行了第二个进程，排列量增加了一倍。

/** @test */
public function itShould_createListTwoUniquePermutationsForOrderItems()
{
    $array = ['a', 'b', 'c', 'd', 'e', 'e', 'f', 'g', 'h'];

    $items = (new ItemPermutations())->listUniquePermutations($array);
    $this->assertEquals(count($items), 181440);
}

第二种方法可以让我获得独特的排列，但即使在切换到数组中搜索字符串而不是数组中的数组时也需要5分钟

/** @test */
public function itShould_createListTwoUniquePermutationsForOrderItems()
{
    $array = ['a', 'b', 'c', 'd', 'e', 'e', 'f', 'g', 'h'];

    $items = (new ItemPermutations())->listUniquePermutations($array);
    $this->assertEquals(count($items), 181440);
}

什么语言可以更快地执行此处理。 python是最好的解决方案吗？

Answer 1

问题不在于语言，而在于代码。通过存储您生成的每个排列并搜索该列表以查看值是否唯一，您的代码在O(n*log(n))甚至O(n²)时间运行，更不用说使用大量内存了。所以无论你将它转换成什么语言，它仍然会非常缓慢。

但是，有一些算法可以在恒定的O(n)时间内生成排列和组合，或者差不多。例如，Heap's Algorithm。

但是，您通过在输入中包含重复条目来复杂化问题，这些条目本身会引入难以处理的2倍重复率。你再一次坚持使用O(n*log(n))或O(n²)将每个条目与其他条目进行比较的任务。

因此，如果您可以将问题空间减少到唯一项目列表，那么您将需要找到一种更有效地处理生成的重复项的方法。

无论如何，我碰巧最近编写了一个实现Heap算法的小型库。你可以找到它on Packagist，但这里是PermutationIterator：

class PermutationIterator {
    /**
     * Given a set of items generate all possible unique arrangements
     * of items. Uses Heap's Algorithm.
     * 
     * @param   array   $set    The set of items on which to operate.
     */
    public static function iterate($set) {
        $state = array_fill(0, count($set), 0);

        yield $set;

        for($i=0, $c=count($set); $i<$c; ) {
            if($state[$i] < $i) {
                if($i % 2 == 0) {
                    self::swap($set, 0, $i);
                } else {
                    self::swap($set, $state[$i], $i);
                }
                yield $set;
                $state[$i]++;
                $i = 0;
            } else {
                $state[$i] = 0;
                $i++;
            }
        }
    }

    /**
     * Swap array items.
     * @ignore
     */
    protected static function swap(&$arr, $a, $b) {
        $t = $arr[$a];
        $arr[$a] = $arr[$b];
        $arr[$b] = $t;
    }
}

例：

foreach( PermutationIterator::iterate(['a', 'b', 'c', 'd', 'e', 'e', 'f', 'g', 'h']) as $comb ) {
    printf("%s\n", json_encode($comb));
}

和time php example.php | wc -l：

362880

real    0m1.853s
user    0m0.027s
sys     0m1.791s