1

我正在尝试用 PHP 编写一个函数来获取所有可能大小的所有排列。我认为一个例子是最好的开始方式：

$my_array = array(1,1,2,3);

不同大小的可能排列：

1
1 // * 见注
2
3
1,1
1,2
1,3
// 以此类推，对于所有大小为 2 的集合
1,1,2
1,1,3
1,2,1
// 以此类推，对于所有大小为 3 的集合
1,1,2,3
1,1,3,2
// 以此类推，对于所有大小为 4 的集合

注意：我不在乎是否有重复。出于本示例的目的，已省略所有未来的重复项。

到目前为止我在 PHP 中所拥有的：

function getPermutations($my_array){

$permutation_length = 1;
$keep_going = true;    

while($keep_going){
    while($there_are_still_permutations_with_this_length){
        // Generate the next permutation and return it into an array
        // Of course, the actual important part of the code is what I'm having trouble with.
    }
    $permutation_length++;
    if($permutation_length>count($my_array)){
        $keep_going = false;
    }
    else{
        $keep_going = true;
        }
}

return $return_array;

}

我能想到的最接近的事情是改组数组，挑选前 n 个元素，查看它是否已经在结果数组中，如果不是，将其添加，然后在数学上没有更多可能的排列时停止该长度. 但它丑陋且资源效率低下。

任何伪代码算法将不胜感激。

此外，对于超级骗子（毫无价值）的奖励积分，有没有办法只用函数获得 1 个排列，但让它不必重新计算所有先前的排列来获得下一个排列？

例如，我给它传递了一个参数 3，这意味着它已经完成了 3 次排列，它只是生成数字 4，而不重做前面的 3？（传递参数不是必需的，它可以在全局或静态中跟踪）。

我问这个的原因是因为随着数组的增长，可能的组合数量也在增长。可以这么说，一个只有十几个元素的小数据集迅速增长为数万亿种可能的组合，我不想让 PHP 一次在其内存中保存数万亿个排列。

4

4 回答 4

2

抱歉没有 php 代码，但我可以给你一个算法。

它可以用少量的内存来完成，因为你不关心被骗，代码也很简单。

第一：生成所有可能的子集。

如果将子集视为位向量，则可以看到集合和二进制数之间存在 1-1 对应关系。

因此，如果您的数组有 12 个元素，您将有 2^12 个子集（包括空集）。

所以要生成一个子集，你从 0 开始并不断增加直到达到 2^12。在每个阶段，您读取数字中的设置位以从数组中获取适当的子集。

一旦你得到一个子集，你现在可以运行它的排列。

可以按字典顺序生成下一个排列（数组索引，而不是元素本身），如下所示：http: //www.de-brauwer.be/wiki/wikka.php? wakka=Permutations并且可以用最少的方式完成记忆。

您应该能够将这两者结合起来，为您自己提供一个 next_permutation 函数。您可以传入一个包含 12 个元素的数组，而不是传入数字，其中包含先前的排列，可能还有一些关于是否需要转到下一个子集等的更多信息（又是一点点内存）。

实际上，您应该能够找到使用最少内存的非常快速的算法，提供 next_permutation 类型的功能并且不会产生欺骗：在网络上搜索多集排列/组合生成。

希望有帮助。祝你好运！

于 2010-06-11T01:40:09.027 回答
1

我想出的最好的一组函数是一些用户在 php.net 上的 shuffle 函数的评论中提供的。这是链接它工作得很好。

希望它有用。

于 2010-06-11T01:53:21.970 回答
0

问题似乎是试图为每个排列提供索引并具有恒定的访问时间。我想不出一个恒定时间算法，但也许你可以改进这个算法。该算法的时间复杂度为 O(n)，其中 n 是您的集合的长度。空间复杂度应该可以减少到 O(1)。

假设我们的集合是 1,1,2,3，我们想要第 10 个排列。另外，请注意，我们将从 0 到 3 对集合中的每个元素进行索引。按照您的顺序，这意味着首先是单个元素排列，然后是两个元素，依此类推。我们将从数字 10 中减去，直到我们可以完全确定第 10 个排列。

首先是单元素排列。其中有 4 个，因此我们可以将其视为从 10 中减去 4 次。剩下 6 个，因此显然我们需要开始考虑两个元素的排列。其中有 12 个，我们可以将其视为从 6 中减去 3 到 4 次。我们发现第二次减去 3 时，我们剩下 0。这意味着我们排列的索引必须是 2（因为我们减去 3 两次）和 0，因为 0 是余数。因此，我们的排列必须是 2,1。

除法和模数可以帮助你。

如果我们正在寻找第 12 个排列，我们会遇到余数为 2 的情况。根据您想要的行为，排列 2,2 可能无效。然而，解决这个问题非常简单，因为我们可以很容易地检测到索引 2 和 2（不要与元素混淆）是相同的，所以第二个应该被撞到 3。因此第 12 个排列可以很简单计算为 2,3。

现在最大的困惑是索引和元素值恰好匹配。我希望我的算法解释不会因此而过于混乱。如果是这样，我将使用您的示例以外的集合并重新编写内容。

于 2010-06-11T16:47:05.753 回答
0

输入：排列索引 k，索引集 S。

伪代码：

L = {S_1}
for i = 2 to |S| do
 Insert S_i before L_{k % i}
 k <- k / i
loop
return L

该算法也可以轻松修改以处理重复项。

于 2010-06-14T12:42:31.357 回答