一组给定数字的排列

有人可以解释一个好的算法，以有效的方式找到给定数字集的所有排列吗？

Answer 1

最简单的方法是递归方法，即可执行伪代码;

def permute(theseq): if len(theseq) <= 1: yield theseq return for i in range(len(theseq)): theseq[0], theseq[i] = theseq[i], theseq[0] for subperm in permute(theseq[1:]): yield theseq[:1] + subperm theseq[0], theseq[i] = theseq[i], theseq[0] 

如果你不熟悉可执行的伪代码 ，符号[1:]和[:1]意味着表示“切片”（分别是“除第一个以外的所有”和“仅仅是第一个”），以及两个相同的赋值执行“交换第0和第i项”和“将它们放回原位”的任务（即再次交换;-)。 yield意味着“提供这个结果但是在迭代时准备继续”，而return意味着“我们都完成了，再见！”。

在不同的性能轴上有一些更好的方法，但第一个里程碑是确保你完全熟悉基本的递归方法并彻底理解它 - 所以我现在停在这里。 如果你完全理解这种方法，为什么它会很好，花花公子， 以及如何以及为什么它在性能上看起来不是最佳，我会很乐意扩展这个答案！ - ）

Answer 2

http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Answer 3

我对Alex的伪代码的实现：

  private int length; private List> permutations; public List> Generate(List list) { length = list.Count; permutations = new List>(); foreach(List subperms in Recursive(list)) permutations.Add(subperms); return permutations; } private List> Recursive(List list) { List> subperms = new List>(); if (list.Count <= 1) { subperms.Add(list); return subperms; } for (int i = 0; i < list.Count; i++) { string temp = list[0]; list[0] = list[i]; list[i] = temp; List tail = new List(list); tail.RemoveAt(0); List head = new List(); head.Add(list[0]); foreach (List subperm in Recursive(tail)) { List headCopy = new List(head); headCopy.AddRange(subperm); if (headCopy.Count == length) permutations.Add(headCopy); else subperms.Add(headCopy); } temp = list[0]; list[0] = list[i]; list[i] = temp; } return subperms; } 

Answer 4

你看过Knuth的“计算机编程艺术”吗？ 第3卷，排序和搜索涵盖了它，这是有道理的，因为排序会创建数据的特定排列。

警惕找到所有组合或排列的组合（和置换）算法。 它们具有非常昂贵的Big-O表示法成本。