순열(Permutation) 알고리즘 Java로 구현하기

안녕하세요. Message입니다.

오늘은 순열 알고리즘을 Java로 구현하는 부분에 대해 간단히 포스팅 하고자 합니다.

개인적으로 조합보다 순열 알고리즘을 이해하는데 좀 더 시간이 걸렸고, 생각해야 될 부분이 다소 있다고 생각되네요.

 

 

1. n개 중에서 r개를 선택한다.

순열은 n개에서 r개를 선택하는 알고리즘입니다.

단순히 3~4개를 가지고 경우의 수를 만드는 케이스라면 알고리즘까지 구현할 필요성을 전혀 못느끼겠으나,

10개만 넘어가도 경우의 수가 엄청나게 불어나기 때문에 알고리즘 구현이 필수적입니다.

순열은 아래와 같이 2가지로 분류할 수 있습니다.

=====

① 중복을 허용하지 않고 n개중에 r개 뽑기

② 중복을 허용하여 n개중에 r개 뽑기

=====

 

중복 허용과 비허용이 그저 순열 알고리즘을 더 어렵게 만드는 부분이라고 생각될 수 있지만

실제로 선택해야 될 아이템들에 따라 개발자에게는 매우 중요한 요소가 될 수 있습니다.

 

 

2. 재귀함수 + ArrayList를 이용한 순열

순열의 점화식을 살펴보면 아래와 같습니다.

0 ≤ r ≥ n을 만족하는 정수 n, r이 있을 때, 순서를 고려하여 r개의 원소를 뽑음

=====

P(n, r) = n(n-1)(n-2) ... (n-r+1)

P(n, r) = n! / (n-r)!

=====

 

단순히 개수를 고려한다면 당장 n에 숫자를 대입하여 풀 수 있겠으나,

이를 코드로 구현하기 위해서는 집합에 있는 특정 아이템을 일일이 매칭해주어야 하므로

우리는 코딩의 관점에서 위의 점화식의 n을 자료구조 안에 들어있는 원소로 생각할 필요가 있습니다.

예를 들면 아래와 같이 생각을 확장할 수 있겠습니다.

=====

① P(5, 3) = 5 × 4 × 3

② P(5, 3) = 5개의 아이템중 1개를 선택 × 4개의 아이템중 1개를 선택 × 3개의 아이템중 한개를 선택

③ P(5, 3) =

[ 1, 2, 3, 4, 5 ] 중에서 '1' 선택 × [ 2, 3, 4, 5 ] 중에서 '2' 선택 × [ 3, 4, 5 ] 중에서 '3' 선택 = 123

[ 1, 2, 3, 4, 5 ] 중에서 '1' 선택 × [ 2, 3, 4, 5 ] 중에서 '2' 선택 × [ 3, 4, 5 ] 중에서 '4' 선택 = 124

[ 1, 2, 3, 4, 5 ] 중에서 '1' 선택 × [ 2, 3, 4, 5 ] 중에서 '2' 선택 × [ 3, 4, 5 ] 중에서 '5' 선택 = 125

[ 1, 2, 3, 4, 5 ] 중에서 '1' 선택 × [ 2, 3, 4, 5 ] 중에서 '3' 선택 × [ 2, 4, 5 ] 중에서 '2' 선택 = 132

[ 1, 2, 3, 4, 5 ] 중에서 '1' 선택 × [ 2, 3, 4, 5 ] 중에서 '3' 선택 × [ 2, 4, 5 ] 중에서 '4' 선택 = 134

[ 1, 2, 3, 4, 5 ] 중에서 '1' 선택 × [ 2, 3, 4, 5 ] 중에서 '3' 선택 × [ 2, 4, 5 ] 중에서 '5' 선택 = 135

....(모든 경우의 수를 구할때 까지 반복)

※ 선택된 아이템은 바로 출력하거나, 모든 아이템이 fix된 이후에 출력해도됨, 확정이라고 생각해도 무방함

=====

 

무언가 반복적인 패턴이 보인다면, 이를 재귀적으로 구현할 수 있을겁니다.

'주어진 자료구조에서 원소를 선택' 하는 기능을 구현하고,

다음 호출되는 재귀함수에 선택한 아이템을 뺀 나머지 집합을 넘겨주면 될 것 같습니다.

주의해야할 점은, 재귀함수가 끝난 이후에는 그 다음 계산을 위하여 remove한 원소를 다시 원래 index에 넣어줘야 하는 점입니다.

import java.util.ArrayList;
import java.util.Arrays;
 
public class Permutation {
 
    private int n; // nPr의 n
    private int r; // nPr의 r
    private ArrayList<Integer> itemList;
    private int[] res;
    
    // 초기화
    public Permutation(int[] intArr, int r){
        this.r = r;             // nPr의 r
        this.n = intArr.length; // nPr의 n
        this.res = new int[r];  // 결과값 배열
        
        // 아이템이 들어갈 리스트
        itemList = new ArrayList<Integer>();
        for(int item : intArr)
            itemList.add(item);
    }
    
    public void perm(int depth){
        perm(itemList, 0);
    }
 
    public void perm(ArrayList<Integer> itemList, int depth) {
        
        // depth가 0부터 시작했을 경우 depth == r에서 리턴
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            return;
        }
        
        for (int i = 0; i < n-depth; i++){
            res[depth] = itemList.remove(i); // 아이템 선택 + 리스트에서 제거
            perm(itemList, depth+1);         // 재귀호출
            itemList.add(i, res[depth]);     // 제거된 아이템 복원
        }
    }
    
    public static void main(String[] args) {
 
        int r = 3;
        int[] arr = {1,2,3,4,5};
        
        Permutation main = new Permutation(arr, r);
        main.perm(0);
    }
}

 

 

그렇다면 여기서 중복을 허용한 코드는 어떻게 해야할까요?

삭제하고 다시 복원해주는 부분을 없애고, i의 범위를 0부터 n까지로 수정해주면 됩니다.

public void perm(ArrayList<Integer> itemList, int depth) {
        
    // depth가 0부터 시작했을 경우 depth == r에서 리턴
    if (depth == r) {
        System.out.println(Arrays.toString(res));
        return;
    }
    
    for (int i = 0; i < n; i++){
        res[depth] = itemList.get(i); // 아이템 선택 + 리스트에서 제거
        perm(itemList, depth+1);            // 재귀호출
    }
}

 

 

2. 재귀함수 + 위치변경(swap)을 이용한 순열

위의 코드는 제가 직관적으로 구현한 코드지만, 구글링을 해보면 swap 메소드를 이용한 순열 알고리즘이 많습니다.

요소와 요소를 자리 바꾸고, depth 변수를 이용하여 선택할 수 있는 요소의 범위를 조절합니다.

 

=====

P(4, 2) =

(첫째[depth]↔첫째(i) swap) [ 1, 2, 3, 4 ] 중에서 '1' 선택 × (둘째[depth]↔둘째(i) swap) [ 1, 2, 3, 4 ] 중에서 '2' 선택 = 12

(첫째[depth]↔첫째(i) swap) [ 1, 2, 3, 4 ] 중에서 '1' 선택 × (둘째[depth]↔셋째(i) swap) [ 1, 3, 2, 4 ] 중에서 '3' 선택 = 13

(첫째[depth]↔첫째(i) swap) [ 1, 2, 3, 4 ] 중에서 '1' 선택 × (둘째[depth]↔넷째(i) swap) [ 1, 4, 3, 2 ] 중에서 '4' 선택 = 14

(첫째[depth]↔둘째(i) swap) [ 2, 1, 3, 4 ] 중에서 '2' 선택 × (둘째[depth]↔둘째(i) swap) [ 2, 1, 3, 4 ] 중에서 '1' 선택 = 21

(첫째[depth]↔둘째(i) swap) [ 2, 1, 3, 4 ] 중에서 '2' 선택 × (둘째[depth]↔셋째(i) swap) [ 2, 3, 1, 4 ] 중에서 '3' 선택 = 23

(첫째[depth]↔둘째(i) swap) [ 2, 1, 3, 4 ] 중에서 '2' 선택 × (둘째[depth]↔넷째(i) swap) [ 2, 4, 3, 1 ] 중에서 '4' 선택 = 24

(첫째[depth]↔셋째(i) swap) [ 3, 2, 1, 4 ] 중에서 '3' 선택 × (둘째[depth]↔둘째(i) swap) [ 3, 2, 1, 4 ] 중에서 '2' 선택 = 32

(첫째[depth]↔셋째(i) swap) [ 3, 2, 1, 4 ] 중에서 '3' 선택 × (둘째[depth]↔셋째(i) swap) [ 3, 1, 2, 4 ] 중에서 '1' 선택 = 31

(첫째[depth]↔셋째(i) swap) [ 3, 2, 1, 4 ] 중에서 '3' 선택 × (둘째[depth]↔넷째(i) swap) [ 3, 4, 1, 2 ] 중에서 '4' 선택 = 34

※ 본인과 본인이 swap 하는 부분이 없으면, 최초 케이스가 누락됨 ex) [1, 2, 3, 4]에서 swap되어 [2, 1, 3, 4] 부터 계산 시작

※ depth가 0부터 시작했을 때, depth == r 이 되면 r개 만큼 출력함, 위에서는 r이 2이므로, index가 0~1까지인 원소 2개만 출력

=====

 

위와 같이 구현하기 위해서는

for문을 이용하여 순차적으로 현재 depth 원소와 i 번째 원소를 swap 한 뒤에 (자연스럽게 swap 되어 첫번째로 옮겨진 원소가 선택됨)

다음으로 호출되는 재귀 함수에는 증가된 인덱스(depth+1)를 넘겨주면 범위가 좁혀지면서 문제를 해결할 수 있습니다.

여기서도 주의해야할 점은, swap 메소드 때문에 원소들의 순서가 변경되기 때문에 이를 다시 되돌려 주어야 합니다.

이를 고려한 Java 코드는 아래와 같습니다. 

import java.util.Arrays;
 
public class Permutation {
 
    private int n; // nPr의 n
    private int r; // nPr의 r
    private int[] res;
    
    // 초기화
    public Permutation(int n, int r){
        this.n = n;
        this.r = r;
        res = new int[r];
    }
    
    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    public void perm(int[] arr, int depth) {
        
        // depth가 0부터 시작했을 경우 depth == r에서 리턴
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            return;
        }
        
        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);     // 스왑
            res[depth] = arr[depth]; // 선택된 원소 저장
            perm(arr, depth +1);     // 재귀호출
            swap(arr, depth, i);     // 복원
        }
    }
    
    public static void main(String[] args) {
 
        int r = 3;
        int[] arr = {1,2,3,4,5};
        
        Permutation main = new Permutation(arr.length, r);
        main.perm(arr, 0);
    }
}
 
 

 

 

그렇다면 중복을 허용하는 순열을 알아봅시다.

위에서는 for문 제어부에 있는 i 초기값이 depth 였기 때문에, 깊이가 증가할수록 선택할 수 있는 원소의 개수가 줄었습니다. 

==>  for(int i=depth; i<n; i++)

따라서 i의 초기값을 0으로 변경해주면 depth가 올라가도 선택할 수 있는 원소의 개수가 동일하기 때문에 중복을 허용하게 됩니다.

public void perm(int[] arr, int depth) {
        
    // depth가 0부터 시작했을 경우 depth == r에서 리턴
    if (depth == r) {
        System.out.println(Arrays.toString(res));
        return;
    }
        
    //for (int i = depth; i < n; i++)
    for (int i = 0; i < n; i++) {
        swap(arr, depth, i);     // 스왑
        res[depth] = arr[depth]; // 선택된 원소 저장
        perm(arr, depth +1);     // 재귀호출
        swap(arr, depth, i);     // 복원
    }
}

 

출력해보면 swap 메소드의 영향으로 111, 112, 113... 으로 순서가 이쁘게 출력되진 않지만

중복을 허용하는 경우의 수가 모두 출력됩니다.

이만 포스팅을 마칩니다.

 

 

 

posted By Message

Commit your way to the LORD, trust in him and he will do this. [PSALms 37:5]

redScreen.tistory.com Blog :(