字符数组的每个组合

尝试显示数组字符的每个组合而不重复字母时遇到问题。

public static String[] getAllLists(String[] elements, int lengthOfList) { //initialize our returned list with the number of elements calculated above String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)]; //lists of length 1 are just the original elements if(lengthOfList == 1) return elements; else { //the recursion--get all lists of length 3, length 2, all the way up to 1 String[] allSublists = getAllLists(elements, lengthOfList - 1); //append the sublists to each element int arrayIndex = 0; for(int i = 0; i < elements.length; i++) { for(int j = 0; j < allSublists.length; j++) { //add the newly appended combination to the list allLists[arrayIndex] = elements[i] + allSublists[j]; arrayIndex++; } } return allLists; } } 

上面的代码很完美，但是在这种情况下不止一次地使用每个字母。

我现在被困在如何做到这一点。

Answer 1

这是一个示例实现。 基本上它需要一个字符串并迭代每个字符，将该字符放在前面。 然后它会对其余字符进行递归。 该结构消除了重复字母的问题，因为递归的输入已删除了您已使用过的字符。

我还将结果存储在一个集合中以删除语义等价。 输入’aab’可以切换char 0和char 1，但仍然是’aab’。 我使用TreeSet来保存排序以便更容易地validation输出，但HashSet会更快。

  public static Set permute(String chars) { // Use sets to eliminate semantic duplicates (aab is still aab even if you switch the two 'a's) // Switch to HashSet for better performance Set set = new TreeSet(); // Termination condition: only 1 permutation for a string of length 1 if (chars.length() == 1) { set.add(chars); } else { // Give each character a chance to be the first in the permuted string for (int i=0; i 

示例运行：

  public static void main(String[] args) { for (String s : CharPermuter.permute("abca")) { System.out.println(s); } } 

产生：

 aabc aacb abac abca acab acba baac baca bcaa caab caba cbaa