Java 字符数组的每种组合
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9666903/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Every combination of character array
提问by LmC
Having problems trying to show every combination of a character of array without repeating letters.
尝试在不重复字母的情况下显示数组字符的每个组合时遇到问题。
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;
}
}
The above code works perfect but use's each letter more than once which cant be done in this case.
上面的代码完美无缺，但每个字母都使用不止一次，在这种情况下无法完成。
And i am stuck how to do this now.
我现在被困如何做到这一点。
采纳答案by Eric Grunzke
Here's an example implementation. Essentially it takes a String and iterates over every character, putting that character at the front. It then recurses on the remaining characters. That structure removes your issue of repeated letters, because the input to the recursion has removed the character you've already used.
这是一个示例实现。本质上它需要一个 String 并迭代每个字符，将该字符放在前面。然后它在剩余的字符上递归。该结构消除了重复字母的问题，因为递归的输入已经删除了您已经使用过的字符。
I also stored results in a set to remove semantic equivalences. The input 'aab' can switch char 0 and char 1 but still be 'aab.' I used a TreeSet to preserve ordering for easier verification of the output, but HashSet would be faster.
我还将结果存储在一个集合中以删除语义等价。输入'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;
}
Example run:
示例运行：
public static void main(String[] args)
{
for (String s : CharPermuter.permute("abca"))
{
System.out.println(s);
}
}
Generates:
产生：
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa
