字符数组的每种组合

这是一个示例实现。本质上，它需要一个String并遍历每个字符，然后将该字符放在最前面。然后，它在其余字符上递归。该结构消除了重复字母的问题，因为递归的输入已删除了您已经使用的字符。

我还将结果存储在一个集合中，以消除语义上的对等。输入“ aab”可以切换char 0和char 1，但仍为“
aab”。我使用TreeSet保留顺序以便更轻松地验证输出，但是HashSet会更快。

  public static Set<String> 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<String> set = new TreeSet<String>();    // 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<chars.length(); i++)      {        // Remove the character at index i from the string        String pre = chars.substring(0, i);        String post = chars.substring(i+1);        String remaining = pre+post;        // Recurse to find all the permutations of the remaining chars        for (String permutation : permute(remaining))        {          // Concatenate the first character with the permutations of the remaining chars          set.add(chars.charAt(i) + permutation);        }      }    }    return set;  }

示例运行：

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

产生：

aabcaacbabacabcaacabacbabaacbacabcaacaabcabacbaa