不同大小的排列

Question

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

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

不同大小的可能排列：

1
1 // * See Note
2
3
1,1
1,2
1,3
// And so forth, for all the sets of size 2
1,1,2
1,1,3
1,2,1
// And so forth, for all the sets of size 3
1,1,2,3
1,1,3,2
// And so forth, for all the sets of size 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 个元素，查看它是否已经在结果数组中，如果不是，则将其添加进去，然后在有时停止从数学上讲，该长度不再有可能的排列。但它很丑陋并且资源效率低下。

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

---

Also, for super-duper (worthless) bonus points, is there a way to get just 1 permutation with the function but make it so that it doesn't have to recalculate all previous permutations to get the next?

比如我给它传递了一个参数3，也就是说它已经做了3次排列，它只是生成数字4，而不重做之前的3个？ （传递参数不是必需的，它可以在全局或静态中跟踪）。

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

Answer 1

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

它可以用少量的内存来完成，并且由于您不关心欺骗，因此代码也很简单。

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

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

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

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

一旦获得一个子集，您现在就可以运行它的排列。

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

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

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

希望有帮助。祝你好运！

Answer 2

我想出的最好的一组函数是由某些用户在 php.net 上的 shuffle 函数的评论中提供的函数，这里是 链接 它效果很好。

希望它有用。

Answer 3

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

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

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

除法和模数可能会对您有所帮助。

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

现在最大的困惑是索引和元素值恰好匹配。我希望我的算法解释不会因此而太混乱。如果是的话，我将使用您的示例之外的一组并重写内容。

Answer 4

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

伪代码：

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

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