一个给定的组号码的排列 [英] Permutations of a given set of numbers

问题描述

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

Can someone please explain a good algorithm to find all permutations of a given set of numbers in an efficient manner?

推荐答案

最简单的方法是递归的，即在执行伪code;

The simplest approaches are the recursive ones, i.e., in executable pseudocode;

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]

如果你不熟悉可执行的伪code 的符号 [1：] 和 [1] 是为了表示切片（respecively除第一次和只是第一），以及两个相同的任务执行的交换0级和第i个项目和把它们放回原处的任务（即再次交换他们;-)。 收益率的意思是提供这样的结果，但准备继续迭代时，而返回表示我们都做了，再见！。

in case you're not familiar with executable pseudocode, the notations [1:] and [:1] are meant to denote "slices" (respecively "all but the first" and "just the first"), and the two identical assignments performs the tasks of "swap the 0th and ith items" and "put them back in place" (i.e. swap them again;-). yield means "provide this result but be ready to continue when iterated on", while return means "we're all done, bye bye!".

有沿的表现不同轴某种程度上更好的方法，但第一个里程碑是确保你完全熟悉了基本的递归方法，并了解它彻底的 - 所以我停在这里了。如果当你完全了解这种方法，为什么它铁锅好得很，和如何以及为什么它并没有真正似乎最佳的表现，我会很高兴 展开这个答案 - ！）

There are somewhat better approaches along different axes of performance, but the first milestone is making sure you're totally familiar with the fundamental recursive approach and understand it thoroughly -- so I'm stopping here for now. If and when you do fully understand this approach, why it woks just fine and dandy, and how and why it doesn't really seem optimal in performance, I'll be happy to expand on this answer!-)

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