Смешайте несколько строк во все возможные комбинации

Question

У меня есть несколько строк.

1. 1

2. 2

3. 3

Как объединить их во все свои уникальные комбинации?

1. 123

2. 132

3. 213

4. 231

5. 312

6. 321

Вот код, у меня есть, но я хотел бы работать без Random класса, потому что я понимаю, что это не самый лучший способ сделать это.

import java.util.Random; 

public class Solution 
{ 
    public static void main(String[] args) 
    { 
     String[] names = new String[]{"string1", "string2", "string3"}; 
     for (int i = 0; i < 9; i++) { 
      Random rand = new Random(); 
      int rand1 = rand.nextInt(3); 
      System.out.println(names[rand.nextInt(3)] + 
        names[rand1] + 
        names[rand.nextInt(3)]); 
     } 
    } 
} 

Answer 1

Вы можете перебрать массив, создав еще один вложенный цикл для каждого повторения.

for (String word1 : words) { 
    for (String word2 : words) { 
     for (String word3 : words) { 
      System.out.println(word1 + word2 + word3); 
     } 
    } 
} 

Вот как избежать того же слова в одной комбинации.

for (String word1 : words) { 
    for (String word2 : words) { 
     if (!word1.equals(word2)) { 
      for (String word3 : words) { 
       if (!word3.equals(word2) && !word3.equals(word1)) { 
        System.out.println(word1 + word2 + word3); 
       } 
      } 
     } 
    } 
} 

Это классная версия, которая может иметь несколько длин, используя обратную трассировку.

import java.util.ArrayList; 
import java.util.List; 


public class PrintAllCombinations { 

    public void printAllCombinations() { 
     for (String combination : allCombinations(new String[] { "A", "B", "C" })) { 
      System.out.println(combination); 
     } 
    } 

    private List<String> allCombinations(final String[] values) { 
     return allCombinationsRecursive(values, 0, values.length - 1); 
    } 

    private List<String> allCombinationsRecursive(String[] values, final int i, final int n) { 
     List<String> result = new ArrayList<String>(); 
     if (i == n) { 
      StringBuilder combinedString = new StringBuilder(); 
      for (String value : values) { 
       combinedString.append(value); 
      } 
      result.add(combinedString.toString()); 
     } 
     for (int j = i; j <= n; j++) { 
      values = swap(values, i, j); 
      result.addAll(allCombinationsRecursive(values, i + 1, n)); 
      values = swap(values, i, j); // backtrack 
     } 
     return result; 
    } 

    private String[] swap(final String[] values, final int i, final int j) { 
     String tmp = values[i]; 
     values[i] = values[j]; 
     values[j] = tmp; 
     return values; 
    } 

} 

Обратите внимание, что при использовании случайного метода никогда не гарантируется получение всех комбинаций. Поэтому он должен всегда перебирать все значения.

Answer 2

Вы можете использовать библиотеку Google Guava, чтобы получить все перестановки строк.

Collection<List<String>> permutations = Collections2.permutations(Lists.newArrayList("string1", "string2", "string3")); 
    for (List<String> permutation : permutations) { 
     String permutationString = Joiner.on("").join(permutation); 
     System.out.println(permutationString); 
    } 

Выход:

string1string2string3 
string1string3string2 
string3string1string2 
string3string2string1 
string2string3string1 
string2string1string3 

Answer 3

Во-первых, нет ничего случайного в результате вы после - и Random.nextInt() не даст вам уникальные перестановки, или обязательно все перестановки.

Для N элементов, есть N! (N -факториальные) уникальные последовательности, которые, я считаю, являются тем, чем вы являетесь. Поэтому ваши три элемента дают шесть уникальных последовательностей (3! = 3 * 2 * 1).

Это потому, что у вас есть выбор из трех элементов для первой позиции (N), то выбор из двух оставшихся элементов для второй позиции (N-1), в результате чего один неизбранный элемента для последней позиции (N-2).

Таким образом, это означает, что вы должны иметь возможность выполнять итерацию по всем перестановкам последовательности; и следующий код должны сделать это для последовательности из 3 элементов:

// Select element for first position in sequence... 
for (int i = 0 ; i < 3 ; ++i) 
{ 
    // Select element for second position in sequence... 
    for (int j = 0 ; j < 3 ; ++j) 
    { 
     // step over indices already used - which means we 
     // must test the boundary condition again... 
     if (j >= i) ++j; 
     if (j >= 3) continue; 

     // Select element for third position in sequence... 
     // (there is only one choice!) 
     for (int k = 0 ; k < 3 ; ++k) 
     { 
      // step over indices already used, recheck boundary 
      // condition... 
      if (k >= i) ++k; 
      if (k >= j) ++k; 
      if (k >= 3) continue; 

      // Finally, i,j,k should be the next unique permutation... 
      doSomethingWith (i, j, k); 
     } 
    } 
} 

Теперь, большой оговоркой, что я только что написал эту ОТН, так что никаких guarentees. Однако, надеюсь, вы увидите, что вам нужно сделать. Разумеется, это можно и нужно обобщить для поддержки размеров суровых размеров, и в этом случае вы можете заполнить int[] индексами для последовательности.

Однако, я думаю, что если вы посмотрите вокруг, будут созданы более эффективные алгоритмы для генерации перестановок последовательности.