查找 n 个字母表的所有排列的算法

Question

我编写了以下算法来查找 n 个唯一字母表的所有可能排列。

Set<String> results = new HashSet<String>();
    int size = 1;
            //find the total permutations possible
    for(int i=0;i<array.length;i++){
        size*=(i+1);            
    }
    // i is the number of items remaining to be shuffled.
    while(results.size()<size){
        for (int i = array.length; i > 1; i--) {
            // Pick a random element to swap with the i-th element.
            int j = rng.nextInt(i);  // 0 <= j <= i-1 (0-based array)
            // Swap array elements.
            char tmp = array[j];
            array[j] = array[i-1];
            array[i-1] = tmp;
        }
        StringBuffer str = new StringBuffer();          
        for(int i=0;i<array.length;i++)
            str.append(array[i]);
        results.add(str.toString());
    }
    System.out.println(results);

1) 有什么办法可以改进这个算法吗？
2）该算法的时间复杂度是多少？

PS：我向那些对我的上一篇文章做出反应的人表示歉意。在寻求帮助之前我会自己尝试。

Answer 1

通过利用随机洗牌，您将进行大量次迭代，但最终不会实际将新项目放入集合中 - 您应该寻找一种方法，确保在每次迭代中新项目被放入集合中（我所说的“新”只是指以前从未见过的排列）。

我不想猜测上面提供的算法的时间复杂度 - 它会很大。

Answer 2

1）有什么办法可以改进这个算法吗？

是的。只是为了给您一些如何确定性地生成排列的提示：

• 想象一下 N 元素上所有排列的字典顺序。想象一下，在给定前一个排列的情况下，如何按该顺序生成下一个排列

• 想象一下，考虑到具有公共前缀的一组排列（例如，435 126、435 162 等）是什么以及如何在算法中使用它。

Answer 3

生成排列的最佳方法是迭代地执行此操作：找到一种方案从一个排列转到下一个排列，直到您看到所有排列为止。 Knuth 在 TAOCP 的组合分册之一中公开了这样的方案，并且无需深入研究他的类似汇编的伪代码，您可能需要检查 这些算法的这些漂亮的 C 实现。您正在寻找的算法是生成排列的算法。

与（我所理解的）你的算法相反，这种算法的优点是它是确定性的，并且每次都会生成不同的排列。

Answer 4

感谢您的投入。我想我有更好的算法。请提供意见

private static List<String> allPerms(char[] array) {    
  List<String> perms = new ArrayList<String>();
  if(array.length<=1 )
      perms.add(String.valueOf(array[0]));
  else{
      char[] newarray = Arrays.copyOf(array, array.length-1);
      char lastChar = array[array.length-1];
      List<String> soFar = allPerms(newarray);
      for(int i=0; i<soFar.size(); i++) {       
          String curr = soFar.get(i);
          for(int j=0;j<array.length;j++){
              StringBuffer buff = new StringBuffer(curr);
              perms.add(buff.insert(j, lastChar).toString());                 
          }
      }       
    }
return perms; }