More efficient way to find all combinations?

Say you have a List of Strings or whatever, and you want to produce another List which will contain every possible combination of two strings from th开发者_JS百科e original list (concated together), is there any more efficient way to do this other than using a nested for loop to combine the String with all the others?

Some sample code:

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

The time for execution gets pretty bad pretty quickly as the size of the original list of Strings grows.

Any more efficient way to do this?

---

You can avoid checking i != j condition by setting j = i + 1. Also, things like bytes.length() get evaluated at each iteration of both loops - save it into a value and reuse. Calling a.length() inside the loop asks for a length of the same string multiple times - you can save some runtime on that as well. Here are the updates:

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

Edit: j = i because you want to consider a combination of a string with itself; Also, you'd need to add a.concat(b) as well since this combination is never considered in the loop, but is a valid string

---

You can't get Better than O(N^2), because there are that many combinations. But you could speed up your algorithm a bit (from O(N^3)) by removing the indexOf calls:

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

---

In addition to what Jimmy and lynxoid say, the fact that the total length is constrained gives you a further optimization. Sort your strings in order of length, then for each s you know that you require only the as such that a.length() == targetLength - s.length().

So as soon as you hit a string longer than that you can break out of the inner loop (since all the rest will be longer), and you can start at the "right" place for example with a lower-bound binary search into the array.

Complexity is still O(n^2), since in the worst case all the strings are the same length, equal to half of totalLength. Typically though it should go somewhat better than considering all pairs of strings.