CODEWITHSUNDEEP
javaalgorithmloopscollectionscombinations
LuxuryMode
LuxuryMode

Reputation: 33741

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 the 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?

Upvotes: 0

Views: 2919

Answers (3)

lynxoid
lynxoid

Reputation: 519

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

Upvotes: 3

Steve Jessop
Steve Jessop

Reputation: 279225

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.

Upvotes: 1

Jimmy
Jimmy

Reputation: 91442

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

Upvotes: 3

Related Questions