复杂的打印字符串排列

这是我的代码打印字符串排列。我正在努力计算函数的时间复杂度。有人可以请建议几个指针。如果有更多的时间有效的方法？复杂的打印字符串排列

import java.util.ArrayList; 

public class Permutations { 

    public static void main(String[] args){ 
     ArrayList<String> aList = permutation("ABCC"); 
     for(int i=0; i<aList.size(); i++){ 
      System.out.print(aList.get(i) + " "); 
     } 
    } 

    public static ArrayList<String> permutation(String s) { 
     // The result 
     ArrayList<String> res = new ArrayList<String>(); 
     // If input string's length is 1, return {s} 
     if (s.length() == 1) { 
      res.add(s); 
     } else if (s.length() > 1) { 
      int lastIndex = s.length() - 1; 
      // Find out the last character 
      String last = s.substring(lastIndex); 
      // Rest of the string 
      String rest = s.substring(0, lastIndex); 
      // Perform permutation on the rest string and 
      // merge with the last character 
      res = merge(permutation(rest), last); 
     } 
     return res; 
    } 


    public static ArrayList<String> merge(ArrayList<String> list, String c) { 
     ArrayList<String> res = new ArrayList<String>(); 
     // Loop through all the string in the list 
     for (String s : list) { 
      // For each string, insert the last character to all possible postions 
      // and add them to the new list 
      for (int i = 0; i <= s.length(); ++i) { 
       String ps = new StringBuffer(s).insert(i, c).toString(); 
       res.add(ps); 
      } 
     } 
     return res; 
    } 
}

来源

2014-12-18 Shauny

@DaaaahWhoosh，看起来递归 - 'merge（permutation（rest），last）'。 – ChiefTwoPencils

@ChiefTwoPencils这就是为什么我讨厌递归，它总是发生在一个小行。我的错。 – DaaaahWhoosh

它应该是n^2，因为你在'合并'中有一个嵌套for循环 – Sam

对于速度的提高，一LinkedList会更快，也使用相同的StringBuffer和StringBuffer#setCharAt(int, char)。可能是这样的：

List<String> permutations = new ArrayList<String>(initial size); // initial size to avoid multiple arrays to be created 
if (s.length() == 1) { 
    permutations.add(s); 
} else { 
    StringBuffer sb = new StringBuffer(s); 
    loop { // some kind of loop 
     sb.setCharAt(0, 'a'); // do the next permutation 
     permutations.add(sb.toString()); 
    } 
} 
return permutations;

来源

2014-12-18 19:34:30 Bubletan

只有当您使用#delete操作时，LinkedList才更快。尝试一下，看看LinkedList的实现，知道原因。 – dit

嗯，仍然比构建多个数组更好，也可以为ArrayList设置初始大小。 – Bubletan

是初始大小也是个好主意 – dit

Plain merge()是O（n^2）。复发似乎是O（n^3）

来源

2014-12-18 20:01:22

复杂的打印字符串排列

回答

相关问题