php - 不同大小的排列

Question

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

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

不同大小的可能排列:

11 // * See Note231,11,21,3// And so forth, for all the sets of size 21,1,21,1,31,2,1// And so forth, for all the sets of size 31,1,2,31,1,3,2// And so forth, for all the sets of size 4

Note: I don't care if there's a duplicate or not. For the purposes of this example, all future duplicates have been omitted.

What I have so far in 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 个元素，看看它是否已经在结果数组中，如果不是，则添加它，然后在数学上没有更多可能的排列时停止对于那个长度。但它丑陋且资源效率低下。

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

---

此外，对于 super-duper(毫无值(value)的)奖励积分，是否有一种方法可以仅使用该函数获得 1 个排列，但使其不必重新计算所有先前的排列来获得下一个排列？

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

我问这个的原因是因为随着数组的增长，可能的组合数量也会增加。只要说一个只有十几个元素的小数据集会迅速增长到数万亿种可能的组合就足够了，我不想让 PHP 承担一次在其内存中保存数万亿个排列的任务。

Answer 1

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

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

首先:生成所有可能的子集。

如果把子集看成位向量，可以看到集合和二进制数是一一对应的。

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

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

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

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

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

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

希望对您有所帮助。祝你好运!