순열 Permutation (Java) 2가지 방법(swap, visited)

 

1. Swap 을 이용한 순열

// 순서 없이 n 개중에서 r 개를 뽑는 경우
// perm(arr, 0, n, r);
static void perm(int[] arr, int depth, int n, int r) {
    if (depth == r) {
        print(arr, r);
        return;
    }
 
    for (int i=depth; i<n; i++) {
        swap(arr, depth, i);
        perm(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;
}

 

2. Visited 배열을 이용한 순열

// 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
// perm(arr, output, visited, 0, n, r);
static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
    if (depth == r) {
        print(output, r);
        return;
    }
 
    for (int i=0; i<n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            output[depth] = arr[i];
            perm(arr, output, visited, depth + 1, n, r);
            visited[i] = false;;
        }
    }
}

 

 

 

 

출처 : https://bcp0109.tistory.com/m/14

순열 Permutation (Java)