代码之家 › 专栏 › 技术社区 › Srini Kandula

求n个字母的所有排列的算法

permutation algorithm java

Srini Kandula · 技术社区 · 14 年前

我编写了下面的算法来查找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) 这个算法的时间复杂度是多少?

previous post . 我先自己试试再求助。

4 回复 | 直到 7 年前

Will A 14 年前

通过使用随机洗牌,您将有一个 大量的 最终没有将一个新项目放入集合的迭代次数-您应该寻找一种方法,确保每次迭代都将一个新项目放入集合中(所谓“new”,我只是指以前没有见过的排列)。

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

jpalecek 14 年前

1) 有什么可以改进这个算法的吗?

对。只是给你一些提示,你如何确定地产生排列:

N 元素。想象一下,在给定前一个排列的情况下,如何按照这个顺序生成下一个排列
435 435 162等)以及如何在算法中使用它。

Jérémie 14 年前

生成置换的最佳方法是迭代进行:找到一个方案,从一个置换到下一个置换,直到看到所有置换。Knuth在TAOCP的一个组合分册中公开了这样一个方案,不必像伪代码一样进入他的程序集,您可能需要检查 these nifty C implementation of those algorithms . 您正在寻找的算法是生成置换的算法。

这种算法的优点在于它是确定性的,每次都会产生不同的排列。

Srini Kandula 14 年前

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; }