가능한 모든 조합에 여러 문자열을 섞습니다.

Question

일부 문자열이 있습니다.

1. 1 나는 그들의 독특한 조합으로 그들을 결합 어떻게 3

2

?

1. 123

2. 132

3. 213

4. 231

5. 312

여기

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 -factorial) 독특한 시퀀스 - 나는 당신이 무엇을하고 있는지 믿습니다. 따라서 세 개의 요소는 여섯 개의 고유 시퀀스 (3! = 3 * 2 * 1)를 제공합니다.첫 번째 위치 (N)에 대한 세 가지 요소의 선택의 여지가 있기 때문에

이

이며, 다음 마지막 위치 ( N-2)에 대해 하나 개의 unchosen 요소를 떠나 두 번째 위치 ( N-1)의 나머지 두 요소의 선택.

따라서 시퀀스의 모든 순열을 반복 할 수 있어야합니다. 다음 코드는 는 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); 
     } 
    } 
} 

지금, 나는 그냥이 OTH를 쓴 큰주의, 그래서 guarentees합니다. 그러나, 당신이해야 할 일을 잘 알 수 있습니다. 물론 이것은 임의의 세트 크기를 지원하기 위해 일반화 될 수 있고 또 그렇게되어야합니다.이 경우 int[]에 시퀀스의 색인을 채울 수 있습니다.

그러나 주위를 둘러 보면 시퀀스의 순열을 생성하는 데 더 좋은 알고리즘이 있다고 생각합니다.