5

我目前正在计算一组数据的唯一排列。虽然以下代码正在运行，但它并没有我想要的那么高效。一旦我得到超过 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，它会运行超过 100k 次，然后才能找到 840 个唯一排列。

我想找到一种方法来减少这种情况并找到通往唯一排列的最短路径。感谢您提供的任何帮助或建议。

4

4 回答 4

5

所以我花了更多时间思考这个问题，这就是我想出的。

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

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

于 2013-09-25T03:49:33.163 回答
2

我刚刚在wiki上尝试了“按字典顺序生成”的方式，它为您的“1,2,2,3,4,4,4,4”样本生成了相同的结果，所以我猜它是正确的。这是代码：

function &permuteUnique($items) {
    sort($items);
    $size = count($items);
    $return = [];
    while (true) {
        $return[] = $items;
        $invAt = $size - 2;
        for (;;$invAt--) {
            if ($invAt < 0) {
                break 2;
            }
            if ($items[$invAt] < $items[$invAt + 1]) {
                break;
            }
        }
        $swap1Num = $items[$invAt];
        $inv2At = $size - 1;
        while ($swap1Num >= $items[$inv2At]) {
            $inv2At--;
        }
        $items[$invAt] = $items[$inv2At];
        $items[$inv2At] = $swap1Num;
        $reverse1 = $invAt + 1;
        $reverse2 = $size - 1;
        while ($reverse1 < $reverse2) {
            $temp = $items[$reverse1];
            $items[$reverse1] = $items[$reverse2];
            $items[$reverse2] = $temp;
            $reverse1++;
            $reverse2--;
        }
    }
    return $return;
}

分析您的示例输入的时间：上述方法：2600,3000,3000,2400,2400,3000；您的“调用 permuteUnique：2647”方法：453425.6,454425.4,454625.8。在您的此示例输入中，它的速度大约快 500 倍 :) 如果您正在逐个处理结果（我猜您会的），使用这种非递归方法，您可以处理生成的一个，然后生成下一个（而不是在处理之前生成所有并存储所有）。

于 2013-09-25T14:12:27.460 回答
0

试试这个修改后的迭代版本。它没有递归开销。

发现于： http ://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

原来的：

function pc_next_permutation($p, $size) {
    // slide down the array looking for where we're smaller than the next guy
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }

    // slide down the array looking for a bigger number than what we found before
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }

    // swap them
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

    // now reverse the elements in between by swapping the ends
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
      $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }

    return $p;
}

$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;

do { 
    foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);

foreach ($perms as $p) {
    print join(' ', $p) . "\n";
}

这是将其修改为不同排列的一种想法，但我认为有更快的解决方案....

function pc_next_permutation($p, $size) {
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }
    if ($i == -1) { return false; }
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
      $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }

    return $p;
}

$uniqueMap=array();
$set  = split(' ', '1 2 2 3 4 4 4 4');
$size = count($set) - 1;
$perm = range(0, $size);
$j=0;

do { 
    $uniqueSetString="";
    foreach ($perm as $i) 
        $uniqueSetString .= "|".$set[$i];

    if (!isset($uniqueMap[$uniqueSetString]))
    {
       foreach ($perm as $i)
           $perms[$j][] = $set[$i];

       $uniqueMap[$uniqueSetString]=1;
    }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);

foreach ($perms as $p) {
    print join(' ', $p) . "\n";
}
于 2013-09-27T19:24:45.727 回答
0

您需要的是factoriadic，它允许您生成第 n 个排列，而不必生成所有前面/后面的排列。我已经用 PHP 对其进行了编码，但我的 ATM 上没有，抱歉。

编辑：给你，它应该让你开始。

于 2013-09-28T23:55:53.177 回答