Java에서 주어진 문자열의 모든 순열 찾기

순열은 배열의 순서가 중요 할 때 세트에서 가능한 배열의 수를 결정하는 수학적 기술입니다.

재귀를 사용한 문자열의 순열

permutationFinder(String str)함수는 전달 된 문자열의 모든 순열을 인쇄하는 재귀 적입니다. Set변수는 중복 항목이 자동으로 제거되도록 Java 문자열의 순열을 저장하는 데 사용됩니다. 우리는 문자열에서 한 번에 한 글자 씩 단어를 자르고 나머지 글자를 따로 처리합니다.

insertChar함수는 전달한 문자열의 전체 순열 목록을 얻기 위해 첫 번째 문자를 삽입합니다.

문자열 “ABC"로 시작하여 한 번에 한 글자 씩 반복합니다. 초기 문자A를 분리하고 나머지는BC입니다. 이제rem을 반복하고 나머지 문자에 대한 순열을 찾습니다. 프로세스는 아래에 자세히 설명되어 있습니다.

permutationFinder()함수는 잘라낼 것이 없을 때까지 실행됩니다. 이것이 우리가rem = ""를 얻는 이유입니다. 이 시점에서""를perms에 추가하고 반환합니다.이 값은Set변수words에 추가로 저장됩니다. 또한이 순간의initial문자는C임을 기억하십시오.

Set단어의 각 문자열을 반복합니다. 우리는""빈 문자열로strNew를 가지고 있으며,이 경우 두 번째 for 루프로 내려갑니다.strNew.length()와 같은i=0이 있습니다. 따라서 해당 지점의 인수를 사용하여insertChar("",C,0)메서드를 호출합니다. 이 호출은perm에 추가 된C를 리턴합니다.

우리는 고리를 깨고 미완성 사업이 있는지 확인합니다. 따라서이 시점에서initial값은B로,단어에는C라는 하나의 요소가 있습니다. 이제C를 사용하여 다른 위치에B를 추가하여 루프를 반복합니다. 따라서Set단어 내에서BC와CB를 두 요소로 얻습니다.

이 시점에서 우리는 루프를 벗어 났고initial값을A로 얻습니다. 이 과정을 더 반복하고 초기 순열의 가능한 위치에 초기 문자A를 삽입합니다. 첫째,BC의 경우ABC``BAC및BCA를 얻습니다. 마찬가지로 두 번째 순열CB의 경우에도 동일한 작업을 수행합니다. 첫 번째 문자를 가능한 위치에 삽입하고ACB,CAB및CBA를 가져옵니다.

import java.util.HashSet;
import java.util.Set;

public class PermutationFinder {
  public static Set<String> permutationFinder(String str) {
    Set<String> perm = new HashSet<String>();
    if (str == null) {
      return null;
    } else if (str.length() == 0) {
      perm.add("");
      return perm;
    }
    char initial = str.charAt(0);
    String rem = str.substring(1);
    Set<String> words = permutationFinder(rem);
    for (String strNew : words) {
      for (int i = 0; i <= strNew.length(); i++) {
        perm.add(insertChar(strNew, initial, i));
      }
    }
    return perm;
  }

  public static String insertChar(String str, char c, int j) {
    String begin = str.substring(0, j);
    String end = str.substring(j);
    return begin + c + end;
  }
  public static void main(String args[]) {
    String s1 = "ABC";
    System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
  }
}

이들은 “ABC"문자열의 가능한 순열입니다.

출력:

Permutations for ABC are: 
[ACB, BCA, ABC, CBA, BAC, CAB]