순열(Permutation)알고리즘 구현

순열 : 서로 다른 n개의 대상에서 r개를 뽑아 일렬로 배열한 것.  (경우의 수 : nPr)

 

1. 순열 알고리즘 

- A, B, C를 모든 경우의 수로 나열하려면

- A를 맨 앞에 두고 나머지 두개를 바꾸는 2가지 + B를 맨 앞에 두고 나머지 두 개를 바꾸는 2가지 + C를 맨 앞에 두고 나머지 두 개를 바꾸는 2가지 = 총 6가지가 된다.

 

 

 

 

- n개의 요소라고 생각하면

1) 0번째 인덱스에 0~n-1까지의 원소를 넣는 경우의 수를 구한다.

ex) 1234, 2134, 3214, 4231 (1,2,3,4 각각이 인덱스 0인 경우들)

 

2) 1번에서 나온 경우에 1번째 인덱스에 1~n-1까지 원소를 넣는 경우를 구한다.

ex) 1234 -> 1234, 1324, 1432 (2,3,4 각각이 인덱스 1인 경우들) / 2134 -> 2134, 2314, 2431

 

3) 위의 과정을 n-1번째 원소까지 반복하여 모든 경우의 수 구한다.

ex) 1234 -> 1234, 1243 / 1324 -> 1324, 1342 ....

 

 

2.nPr 순열

- 위의 적은 과정은 n개의 요소를 모두 나열한 경우의 수고,

- n개 중 r개만 구하고 싶다면 n-1이 아니라, r번만 반복하면 0~r번째까지 돌아서 구할 수 있음

 

void permutation(int[] numbers, int depth, int r) { 
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(numbers[i] + "\t");
            }
            System.out.println();
            return;
        }

        for (int i = depth; i < numbers.length; i++) {
            swap(numbers, depth, i);
            permutation(numbers, depth + 1, r);
            swap(numbers, depth, i);
        }
}
    
void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
}