给定数字集合的排列

Question

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

Answer 1

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

Answer 2

你有没有看克努特“计算机程序设计艺术”？第3卷，排序和搜索覆盖它，这是有道理的，因为排序创建了一个特定的数据排列。

请注意查找所有组合或置换的组合（和置换）算法。它们具有非常昂贵的Big-O符号成本。

Answer 3

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

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] 

的情况下，你不熟悉executable pseudocode，符号[1:]和[:1]是为了表示“切片”（respecively“所有，但第一”和“只是第一”），以及两个相同的任务执行“交换第0项和第i项”和“将它们放回原处”的任务（即再次交换它们;-)。 yield的意思是“提供这个结果，但准备好继续迭代时”，而return的意思是“我们都完成了，再见！”。

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

Answer 4

我的C＃实现亚历克斯的伪代码：的

private int length; 
    private List<List<string>> permutations; 

    public List<List<string>> Generate(List<string> list) 
    { 
     length = list.Count; 
     permutations = new List<List<string>>(); 

     foreach(List<string> subperms in Recursive(list)) 
      permutations.Add(subperms); 

     return permutations; 
    } 

    private List<List<string>> Recursive(List<string> list) 
    { 
     List<List<string>> subperms = new List<List<string>>(); 

     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<string> tail = new List<string>(list); 
      tail.RemoveAt(0); 

      List<string> head = new List<string>(); 
      head.Add(list[0]); 

      foreach (List<string> subperm in Recursive(tail)) 
      { 
       List<string> headCopy = new List<string>(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; 
    }