有效地计算集合中的唯一排列

Question

我目前正在计算数据数组的唯一排列.虽然以下代码正在运行,但它并不像我想的那样高效.一旦我超过6或8个项目,它变得非常慢,我开始遇到内存问题.

这是代码和解释

<?php
function permuteUnique($items, $count = false, $perms = [], &$return = []) {
    if ($count && count($return) == $count) return $return;

    if (empty($items)) {
        $duplicate = false;

        foreach ($return as $a) {
            if ($a === $perms) {
                $duplicate = true;
                break;
            }
        }
        if (!$duplicate) $return[] = $perms;
    } else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
            $newitems = $items;
            $newperms = $perms;
            list($tmp) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $tmp);
            permuteUnique($newitems, $count, $newperms, $return);
        }
        return $return;
    }
}

function factorial($n) {
    $f = 1;
    for ($i = 2; $i <= $n; $i++) $f *= $i;
    return $f;
}

根据输入,[1, 1, 2]我按预期收到以下输出

array (size=3)
  0 => 
    array (size=3)
      0 => int 1
      1 => int 1
      2 => int 2
  1 => 
    array (size=3)
      0 => int 1
      1 => int 2
      2 => int 1
  2 => 
    array (size=3)
      0 => int 2
      1 => int 1
      2 => int 1

该$count参数是这样我可以通过我期望的功能独特的排列数,一旦发现,许多,它可以停止计算并返回数据.这计算为项目总数的阶乘除以所有重复项的计数的阶乘的乘积.我不确定我说得对,所以让我给你举个例子.

给定该集合[1, 2, 2, 3, 4, 4, 4, 4],计算唯一排列的计数, 8! / (2!4!) = 840因为总共有8个项目,其中一个重复两次,另一个重复4次.

现在,如果我将其转换为PHP代码...

<?php
$set = [1, 2, 2, 3, 4, 4, 4, 4];
$divisor = 1;

foreach (array_count_values($set) as $v) {
    $divisor *= factorial($v);
}

$count = factorial(count($set)) / $divisor;
$permutations = permuteUnique($set, $count);

它很慢.如果我将一个计数器放入该permuteUnique函数中,它会在找到840个唯一排列之前运行超过100k次.

我想找到一种方法来减少这种情况并找到最短路径来获得独特的排列.我感谢您提供的任何帮助或建议.

Answer 1

所以我花了一些时间思考这个,这就是我想出来的.

<?php
function permuteUnique($items, $perms = [], &$return = []) {
    if (empty($items)) {
        $return[] = $perms;
    } else {
        sort($items);
        $prev = false;
        for ($i = count($items) - 1; $i >= 0; --$i) {
            $newitems = $items;
            $tmp = array_splice($newitems, $i, 1)[0];
            if ($tmp != $prev) {
                $prev = $tmp;
                $newperms = $perms;
                array_unshift($newperms, $tmp);
                permuteUnique($newitems, $newperms, $return);
            }
        }
        return $return;
    }
}

$permutations = permuteUnique([1, 2, 2, 3, 4, 4, 4, 4]);

以前的统计数据

Uniques: 840
Calls to permuteUnique: 107,591
Duplicates found: 38737
Execution time (seconds): 4.898668050766

新统计数据

Uniques: 840
Calls to permuteUnique: 2647
Duplicates found: 0
Execution time (seconds): 0.0095300674438477

所以我真正做的就是对数据集进行排序,跟踪上一个项目,如果当前项目与之前的项目匹配则不计算排列.我也不再需要预先计算唯一数量并迭代排列以检查重复项.这让世界变得与众不同.