清单一组给定的值的所有排列 [英] Listing all permutations of a given set of values

问题描述

我感兴趣的是不同的技术比较/接近人们可以用它来生成一组给定的所有可能的排列。

I am interested in comparisons of different techniques/approaches one could use to generate all potential permutations of a given set.

推荐答案

您可以表现，特别是分销和简单性之间进行选择。由一个特定的分配我的意思是，你是否在乎一些特定的顺序，如字典，输出的。

You can choose between performance, particular distribution and simplicity. By a particular distribution I mean, whether you care about some particular order, such as lexicographic, of the output.

表现最好的算法，据我所知是豪斯算法。它是最佳的最多在于处理器指令只有一个常数是必要的，以生成一个置换（不计算必要的说明将其打印出来，并不总是需要的话）的感乘法常数

The best performing algorithm to my knowledge is the Steinhaus algorithm. It is optimal up to a multiplicative constant in the sense that only a constant number of processor instructions are necessary to generate one permutation (not counting the instructions necessary to print it out which is not always needed).

还有一个产生的排列在字典序，你可能能够重新塑造为一个递归过程自己，很简单的算法，其性能的 O（n.log（N）.LOG（ n））的的，因此大致相同生成列表通过任何其它方法和排序它

There is also a very simple algorithm that produces the permutations in the lexicographic order that you will probably be able to reinvent as a recursive procedure yourself, and whose performance is O(n.log(n).log(n)), therefore roughly the same as generating the list by any other method and sorting it.

修改：这里是伪$ C $的简单算法的C：

Edit: here is pseudocode of the simple algorithm:

void permute(Element[] permutationPrefix, Set rest)
{
    if (rest.IsEmpty) {
        // permutationPrefix is now a full permutation
        print(permutationPrefix);
    } else {
        foreach (element in rest) {
            permutationPrefix.Append(element);
            permute(permutationPrefix, rest.Minus(element))
            permutationPrefix.Length--;  // cut away the last item
        }
    }
}

最初称这有一个空的排列preFIX 和休息持有全套;如果这集是排序的数据结构，排列将在字典顺序输出。

Initially call this with an empty permutationPrefix and rest holding the full set; if this set is a sorted data structure, the permutations will be output in the lexicographic order.

请注意，我们是复制和修改设置在每次递归调用，这是整个算法的最昂贵的操作，可能连同打印方法。单套拷贝的成本是对数 N 的排列总数;因为递归调用堆栈的深度也对数，在 O（n.log（N）.LOG（N））的性能估计如下：

Note that we are copying and modifying the set at each recursive call, which is the most expensive operation of the whole algorithm, possibly together with the print method. The cost of a single set copy is logarithmic in the total number of permutations n; and because the depth of the recursive call stack is also logarithmic, the O(n.log(n).log(n)) performance estimate follows.

（该算法也适合于转化成表现良好随机排列发生器。）

(This algorithm is also suitable for conversion into a well behaved random permutation generator.)

这篇关于清单一组给定的值的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！