给定长度和字符集，如何得到所有可能的字符串组合

Question

可能重复：
Generating all permutations of a given string

给定长度n=4, 和set of characters -> {'a', 'b'}， 如何编写一些java代码来生成所有可能的字符串，其长度为n，包含集合中的字符？

对于上面的例子中，结果应该有2^4 = 16串，那就是：

aaaa 
aaab 
aabb 
abbb 
baaa 
baab 
babb 
bbbb 
bbaa 
bbab 
bbba 
abaa 
abab 
abba 
baba 
aaba 

这里是我的代码片段：

public void process(String result, String string) 
{ 
    if(string.length() == 0) 
    { 
     System.out.println(result); 
    }else{ 
     for(int i = 0; i < string.length(); i++) 
     { 
      String newResult = new String(result+string.charAt(i)); 
      String newString = new String(string.substring(0,i) + string.substring(i+1, string.length())); 
      process(newResult, newString); 
     } 
    } 
} 

这似乎只是在做置换，而不是我想要什么....... 预先感谢您:)

Answer 1

想想它，你会以同样的方式计算。你在技术上从aaaa到bbbb“计数”，就像二进制一样。

aaaa -> 0000 
aaab -> 0001 
aaba -> 0010 
aabb -> 0011 
... 
bbbb -> 1111 

没有看到你已经尝试了什么，我不能帮你不止于此，但本质上，你需要通过计算你的“最低”的元素，你的“最高”的元素之间枚举所有的“数字”通过他们。

对于更高的元素数量，只要将您的计数视为更高基数的计数。对于八张素，集= {A，B，C，d，E，F，G，H}，你会在什么本质上可以计数八：

aaaa -> 0000 
aaab -> 0001 
... 
aaah -> 0007 
aaba -> 0010 
... 
hhhh -> 7777 

这是你列举所有的组合以同样的方式0-9，长度为4，通过计算从0000到9999

编辑：

感谢您发布您的代码。你是对的，你在做排列。更好的方法是使用与here讨论的算法相同的多重组合（与ordererd组合集合中重复元素的组合）算法。

Answer 2

这可能很容易出错，因为我没有测试过它，但它应该可以工作。即使它没有，它应该非常接近你正在寻找的东西。请注意，第一个for循环填充resultList，而不是设置值，因为没有可以追加的内容。

让我知道是否有问题，我会纠正它。

ArrayList<String> results = new ArrayList<String>(); 
ArrayList<String> components = new ArrayList<String>(){"a","b","c"}; 
int n = 4; 

int size = components.size(); 
for (int j = 0; j < size; j++) 
{ 
    // start with size^(n-1) copies of each letter. 
    for (int i = 0; i < Math.pow(size, n-1); i++) 
    { 
    results.add(components.get(j)); 
    } 
} 

// At this point you have each letter in there once... 

for(int depth = 1; depth < n; depth++) 
{ 
    for(int j = 0; j < size; j++) 
    { 
    String toAppend = components.get(j); 
    for(int i = j; i < results.size(); i += size) 
    { 
     String current = results.get(i); 
     current += toAppend; 
     results.set(i, current); 
    } 
    } 
} 

Answer 3

你已经有了一个答案，但我觉得你需要一些更多的帮助：

if(string.length() == 0) 
{ 
System.out.println(result); 
} 

为什么你会打印一个空字符串？它根本不会打印任何东西。你可能想要打印一条消息并退出你的功能。