Java에서 문자열의 모든 순열 출력하기

다음은 재귀(Recursion)를 활용하여 문자열의 모든 순열(permutation)을 출력하는 Java 프로그램입니다.

예제 코드

public class Demo{
   static void print_permutations(String my_str,String my_ans){
      if (my_str.length() == 0){
         System.out.print(my_ans + " ");
         return;
      }
      boolean my_arr[] = new boolean[26];
      for (int i = 0; i < my_str.length(); i++){
         char ch = my_str.charAt(i);
         String remaining_str = my_str.substring(0, i) + my_str.substring(i + 1);
         if (my_arr[ch - 'a'] == false)
         print_permutations(remaining_str, my_ans + ch);
         my_arr[ch - 'a'] = true;
      }
   }
   public static void main(String[] args){
      String my_str = "hey";
      System.out.println("The permutation of the string are :");
      print_permutations(my_str, "");
   }
}

실행 결과

The permutation of the string are :
hey hye ehy eyh yhe yeh

코드 동작 원리

Demo라는 이름의 클래스 안에는 정적(static) 메서드인 print_permutations가 정의되어 있습니다. 이 메서드는 가장 먼저 입력받은 문자열이 비어 있는지 확인하며, 비어 있다면 지금까지 누적된 결과 문자열을 출력하고 재귀 호출을 종료합니다.

그다음 크기가 26인 불리언(Boolean) 배열 my_arr을 생성합니다. 이 배열은 알파벳 소문자 각각의 사용 여부를 추적하기 위한 것으로, 기본값은 모두 false입니다. 특정 알파벳이 한 번 사용되면 해당 알파벳에 대응하는 배열 인덱스의 값이 true로 변경됩니다. 덕분에 동일한 문자가 여러 번 등장하는 경우에도 중복된 순열이 출력되는 것을 방지할 수 있습니다.

이후 for 루프를 사용하여 문자열의 길이만큼 반복하면서 i번째 문자를 하나씩 선택합니다. 선택된 문자를 제외한 나머지 부분은 remaining_str이라는 새로운 문자열에 저장됩니다. 만약 해당 문자가 아직 사용되지 않은 문자라면, 남은 문자열과 현재까지 만들어진 결과를 인자로 전달하여 메서드를 재귀적으로 호출합니다. 반대로 이미 사용된 문자라면 함수 호출을 건너뛰게 됩니다.

main 메서드에서는 순열을 구할 문자열을 정의한 뒤, 빈 문자열을 두 번째 인자로 넘기며 print_permutations 메서드를 호출하여 전체 과정을 시작합니다.

참고 사항

문자열의 길이가 n일 때 가능한 순열의 개수는 최대 n!개이므로, 문자열이 길어질수록 실행 시간과 출력량이 급격히 증가한다는 점을 유의해야 합니다. 또한 이 코드는 알파벳 소문자 기준으로 작성되었기 때문에, 대문자나 특수 문자가 포함된 문자열을 처리하려면 배열 크기와 인덱스 계산 방식(ch - 'a')을 적절히 수정해야 합니다.