Более эффективный способ найти все комбинации?

Question

Скажем, у вас есть List из Strings или что-то еще, и вы хотите произвести еще один List, который будет содержать каждую возможную комбинацию из двух strings из исходного list (объединенного вместе), есть лиЕсть ли более эффективный способ сделать это, кроме использования вложенного цикла for для объединения строки со всеми остальными?

Пример кода:

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

Время выполнения довольно быстро ухудшается по мере увеличения размера исходного list из Strings.

Есть ли более эффективный способ сделать это?

Answer 1

Вы можете избежать проверки состояния i != j, установив j = i + 1. Кроме того, такие вещи, как 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), так как эта комбинация никогда не рассматривается в цикле, но является допустимой строкой

Answer 2

Вы не можете получить лучше, чем 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));
        }
    }
}

Answer 3

В дополнение к тому, что говорят Джимми и Линксоид, факт ограничения общей длины дает вам дальнейшую оптимизацию.Сортируйте строки по порядку длины, затем для каждого s вы знаете, что вам нужны только a s, такие что a.length() == targetLength - s.length().

Так что, как только вы нажмете на строку длиннее, чем вы можетевырваться из внутреннего цикла (так как все остальные будут длиннее), и вы можете начать с «правильного» места, например, с нижнего бинарного поиска в массиве.

Сложность все еще O (п ^ 2), так как в худшем случае все строки имеют одинаковую длину, равную половине totalLength.Хотя обычно это должно быть несколько лучше, чем рассмотрение всех пар строк.