列出一组给定值的所有排列

Question

我有兴趣对不同的技术/方法进行比较，这些技术/方法可用于生成给定集合的所有潜在排列。

Answer 1

您可以选择性能，特定分布和简单性。我的意思是，你是否关心一些特定的顺序，如词典的输出。

据我所知，效果最好的算法是Steinhaus algorithm。从某种意义上说，只有一个处理器指令是必要的才能生成一个排列（不包括打印它所需的指令并不总是需要），这对于乘法常数是最优的。

还有一个非常简单的算法，它可以按字典顺序生成排列，您可能可以自己重新创建一个递归过程，其性能为O（n.log（n）.log（n ）），因此与通过任何其他方法生成列表并对其进行排序大致相同。

编辑：这里是一个简单的算法的伪代码：

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

最初与空permutationPrefix和rest拿着全套称之为;如果这个集合是一个有序的数据结构，排列将按字典顺序输出。

请注意，我们正在复制和修改每个递归调用中的集合，这是整个算法中最昂贵的操作，可能与print方法一起使用。单套副本的成本是对数排列的总数n;并且因为递归调用栈的深度也是对数的，所以下面是性能估计。

（此算法也适合改装成一个很乖的随机置换生成。）

Answer 2

这个问题已经（其实很多次）提出和回答：

Algorithm to generate all possible permutations of a list?

Permutations with a given integer

就我个人而言，我认为Steinhaus算法正在过度思考问题：它并没有比最天真的实现更快。最天真的实施

类似Java的伪代码：

List<List<Element>> generateAllPermutations(List<Element> input) 
{ 
    List<Element> output = new ArrayList<Element>(); 
    if (input.size() == 0) 
     return output; 
    for (Element first : input) { 
     for (List<Element> sequence : generateAllPermutations(input - first)) 
      output.add(first + sequence); 
    } 
}