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

假设你有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

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

回答

相关问题