JAVA 순열(permutations) 알고리즘

배열의 모든 순열을 재귀적으로 호출하고 출력하는 코드입니다.

 

여기서 사용되는 개념은 백트래킹과 교환(swap)입니다. 이 알고리즘은 재귀적으로 순열을 생성하며, 각 단계에서 현재 위치(i)를 기준으로 나머지 위치(j)를 교환하여 순열을 생성합니다. 이때 백트래킹을 통해 이전 상태로 돌아갈 수 있도록 배열을 다시 원래대로 되돌립니다.

 

/**
  알고리즘
             1,2,3
          /    |   \
        123   213   321           i=0, j=0~2  
      /       |      \
 123,132   213,231   321,312      i=1, j=1~2

 (j가 증가하면서 swap을 한다.)
*/

public class Permutations {
    /**
     * 1,2,3으로 만들 수 있는 모든 경우의 수를 출력한다.
     */
    @Test
    public void 순열(){
        int[] arr = new int[]{1,2,3};
        dfs(0, arr);
    }
    public void dfs(int i, int[] arr){
        //탈출 조건
        if(i == arr.length){
            System.out.printf("%d,%d,%d\n",arr[0],arr[1],arr[2]);
        }

        //재귀
        for(int j=i; j<arr.length; j++){
            swap(j,i,arr);
            dfs(i+1, arr);
            swap(j,i,arr); //backtracking
        }
    }

    private void swap(int i, int j, int[] arr) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

알고리즘 요약

 

순열 메소드: 이 메소드가 시작점입니다. 주어진 초기 배열 [1, 2, 3]을 가지고 dfs 메소드를 호출합니다.

 

dfs 메소드: 깊이 우선 탐색(Depth-First Search)을 구현한 함수로서 재귀적으로 순열을 생성하고 출력합니다.
i는 현재 위치를 나타냅니다. 만약 i가 배열의 길이와 같다면(즉, 모든 위치를 정한 경우), 현재 순열을 출력합니다.
그렇지 않다면, 현재 위치 i부터 배열의 끝까지를 순회하며 순열을 생성합니다.
swap 함수를 통해 현재 위치 i와 j를 교환한 후, 다음 위치로 재귀적으로 진행합니다.
재귀 호출이 끝나면(돌아오면), 다시 swap 함수를 호출하여 배열을 원래대로 되돌립니다. 이는 백트래킹(backtracking)의 개념입니다.

swap 메소드: 두 위치의 원소를 교환하는 함수입니다. 주어진 배열에서 위치 i와 j의 값을 교환합니다.

출력 내용