수학 - 순열( Permutation) JAVA (Visited, swap)

순열 이란 ? 

n개의 값 중에서 r개의 숫자를 모든 순서대로 뽑는 경우의 수이다.

[1,2,3,4] 라는 값 중에서 3개의 숫자만 뽑는 경우의 수는 4P3 이다.

 

• Swap 코드

static void permutation(int[] arr, int depth, int n, int r) {
//[1,2,3,4] , 0 , 4, 3 
    if (depth == r) {
        for (int i = 0; i < r ; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
    }
 
    for (int i=depth; i<n; i++) {
        swap(arr, depth, i);
        permutation(arr, depth + 1, n, r);
        swap(arr, depth, i);
    }
}
 
static void swap(int[] arr, int depth, int i) {
    int temp = arr[depth];
    arr[depth] = arr[i];
    arr[i] = temp;
}

처음 1,2,3,4 가 있으면 1,2,3 을 출력하고 swap 을 한뒤 1,2,4 를 출력 하는 재귀식 방식으로 swap  한다

코드는 Visited 를 활용한 코드보다 간결하지만 순서가 보장되지 않는다.

• Visited 코드

 void permutation(int[] arr, int depth, int[] output, boolean[] visited, int n , int r){ // DFS 완전탐색 알고리즘
        if(depth == r){ // 만약에 뽑을려는 3자리수 일경우 출력
            System.out.println(Arrays.toString(output));
            return;
        }
        for (int i = 0; i < n; i++) {
            // i=0 -> depth -> 0 , output -> [0,0,0] -> depth 는 output 에 들어가는 숫자의 길이라고 생각
            // visited -> [0,0,0,0] -> [f,f,f,f] 라고 생각하면서 [t,f,f,f] visited 를 바꿔가면서 재귀함수를 반복하면서 출력
            if(visited[i] != true){ // 000 0시작
                visited[i] = true; // 100 0 1로 바꾸고 다음 번에 1일경우 하지않음
                output[depth] = arr[i]; // output[0] = arr[0] -> [0,0,0] = 1 -> [1,0,0]
                permutation(arr,depth+1,output,visited,n,r); // ([1,2,3,4] , 1 , [1,0,0] ,[1,0,0,0] (t,f,f,f) , 4, 3 )
                // visited[0]이 t이므로 다음 자리 visitied[1] 으로 시작 하여 다음 자릿수를 찾아감
                visited[i] = false;

            }
        }
  }

visited 코드는 visited[n] 크기의 배열로 방문 할때마다 False -> True로 바꿔가며 

depth == r 일경우 r자리수를 출력 하는 방식이다

재귀적으로 호출하여 종료조건 과 visited 배열의 T/F 변환하는 방식도 알아야함.