找到所有組合的更有效方法？

假設你有Strings的List或什麼的，並且要產生另一個List其中將包含來自兩個strings每一個可能的組合，原來的list（concated在一起），有沒有更有效的方法比使用要做到這一點其他嵌套0循環將字符串與所有其他字符串結合？找到所有組合的更有效方法？

一些示例代碼：

for(String s: bytes) { 
      for(String a: bytes) { 
       if(!(bytes.indexOf(a) == bytes.indexOf(s))) { 
        if(s.concat(a).length() == targetLength) { 
         String combination = s.concat(a); 
         validSolutions.add(combination); 
        } 
       } 
      } 
     }

的執行時間變得很糟糕很快爲的Strings原list生長的大小。

任何更有效的方法來做到這一點？

來源

2011-09-02 LuxuryMode

可能的重複http://stackoverflow.com/questions/7229743/generating-all-possible-combinations –

「IndexOfs」是問題。你能直接比較a和s嗎？ – Jimmy

@Jimmy，我不認爲我可以，因爲有重複的字符串組成一個有效的組合，例如「abc」和「abc」使得「abcabc」，所以如果我做a.equals（s）這不會真的工作爲了我。 – LuxuryMode

可避免通過設置j = i + 1檢查i != j條件。此外，諸如bytes.length()之類的東西在兩個循環的每次迭代中都得到評估 - 將其保存爲值並重用。在循環內調用a.length()會多次請求相同字符串的長度 - 您也可以爲此保存一些運行時。以下是更新：

int len = bytes.length(); 
int aLength; 
String a, b; 
for(int i=0; i<len; i++) { 
    a = bytes[i]; 
    aLength = a.length(); 
    for(int j=i; j<len; j++) { 
    b = bytes[j]; 
    if (b.length() + aLength == targetLength) { 
     validSolutions.add(b.concat(a)); 
     validSolutions.add(a.concat(b)); 
    } 
    } 
}

編輯：j = i，因爲你要考慮自身的字符串的組合;另外，你還需要添加a.concat(b)，因爲這個組合在循環中從來不被考慮，但是是一個有效的字符串

來源

2011-09-02 02:36:56 lynxoid

真棒。我一直在計算操作次數，並使用j = i + 1將操作次數減半。美麗！ – LuxuryMode

如果你只考慮每一對字符串一次，而不是兩次都不要，那麼你不應該把'b.concat（a）'和'a.concat（b）'添加到'validSolutions'嗎？ –

@Steve：你說得對，好點 – lynxoid

你不可能比O（N^2）更好，因爲有很多組合。但你可以（從O（N^3））通過移除indexOf電話有點加快你的算法：

for(int i=0; i<bytes.length(); i++) { 
    for(int j=0; j<bytes.length(); j++) { 
     string s = bytes[i]; 
     string a = bytes[j]; 
     if (i != j && s.length() + a.length() == targetLength) { 
      validSolutions.add(s.concat(a)); 
     } 
    } 
}

來源

2011-09-02 02:17:45 Jimmy

啊哈！對！看起來不錯。 – LuxuryMode

除了Jimmy和lynxoid所說的，總長度受限的事實給了你一個進一步優化。按照長度排序字符串，然後對於每個s，您知道只需要a s，例如a.length() == targetLength - s.length()。

因此，只要你擊中一個比這個長的字符串，你就可以跳出內部循環（因爲所有其他的將會更長），並且你可以從「右邊」的地方開始，例如下界二進制搜索到數組中。

複雜性仍然是O（n^2），因爲在最壞的情況下，所有的字符串都是相同的長度，等於totalLength的一半。通常，雖然它應該比考慮所有的字符串對要好一些。

來源

2011-09-02 03:02:39

對！我有他們按長度排序。偉大的一點！ – LuxuryMode

找到所有組合的更有效方法？

回答

相關問題