給定長度和字符集，如何得到所有可能的字符串組合

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); 
} 

爲什麼你會打印一個空字符串？它根本不會打印任何東西。你可能想要打印一條消息並退出你的功能。