给定数字集的排列

Question

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

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"的任务和ith项目"和"将它们放回原位"(即再换掉它们;-). yield意思是"提供这个结果,但在迭代时准备继续",同时return意味着"我们都完成了,再见!".

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

Answer 2

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