Java - 순열 조합 알고리즘

◎ 순열(permutation)이란

서로다른 n 개의 값 중에서 r 개의 숫자를 선택 후 나열하는 것이다.

 

ex) [1,2,3,4]인 4개의 원소로 이루어진 배열에서, 2개의 숫자를 뽑아 나열하는 경우는

(1,2)(1,3)(1,4)(2,1)(2,3)(2,4)(3,1)(3,2)(3,4)(4,1)(4,2)(4,3) 로 12개이다.

 

---

◎ 순열의 알고리즘적 구현 1 - swap을 이용한 구현

 

배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap한다.

depth 를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고

depth 보다 인덱스가 큰 값들만 가지고 다시 swap 을 진행합니다.

 

 

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

한 줄씩 내려갈때마다 새로운 재귀함수로 들어간것이고 새로운 재귀함수에 들어갈 때마다 depth++이 된다. 파란색 박스는 "depth 를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고"에 의해 고정된 값을 나타낸다. depth가 r과 같아진 경우 출력한다.

 

코드:

public class Main {
    
    public static void main(String[] args) {
        int arr[] = {1,2,3,4}; //뽑을 배열
        per permutation = new per();
        permutation.permutation(arr, 0, 2); //arr에 있는 숫자들중 2개 순열로 뽑기
       
        System.out.print("총 개수: ");
        System.out.println(permutation.count);
    }
}

class per{
    public int count; //순열 경우의 수
        
    public per(){
        this.count = 0;
    }
        
        
    //permutation: arr에 있는 숫자들 중 r개 순열로 뽑기
    public void permutation(int[] arr, int depth, int r){
        if(depth==r){ //depth와 r이 같아지면 출력
            for(int i = 0; i < r; i++){
                System.out.print(arr[i]);
                System.out.print(" ");
            }
            System.out.println();
            count++;
            return;
        }
        for(int i = depth; i<arr.length; i++){
            this.Swap(arr, depth, i);
            this.permutation(arr, depth+1, r); //재귀함수 들어갈때 depth+1
            this.Swap(arr, depth, i); //복구
        }
        
        }
            
    public void Swap(int[] arr, int index1, int index2){
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}

 

결과:

1 2
1 3
1 4
2 1
2 3
2 4
3 2
3 1
3 4
4 2
4 3
4 1
총 개수: 12

 

위의 결과를 보면 알 수 있듯이, 이 방법은 순열의 경우의 수가 사전적으로 정렬되어 나오지 않는다.

 

---

◎ 순열의 알고리즘적 구현 2 - Visited 배열을 이용해 DFS로 구현

 

DFS를 돌면서 모든 인덱스를 방문하여 craft 에 값을 넣고 넣은 값의 visited값을 true로 바꾼다.

visited값이 false인 값을 넣는다. depth 값은 craft 에 들어간 숫자의 길이이다.

depth 의 값이 r 만큼 되면 craft 에 들어있는 값을 출력

 

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

한 줄씩 내려갈때마다 새로운 재귀함수로 들어간것이고 새로운 재귀함수에 들어갈 때마다 depth++이 된다. 파란색 박스는 craft에 들어간 숫자를 나타낸다.

 

코드:

 

public class Main {
    
    public static void main(String[] args) {
        int arr[] = {1,2,3,4};
        int r = 2;
        //4개중 2개 뽑아 나열
        per permutation = new per();
        permutation.permutation(arr, 0 ,r, new boolean[arr.length], new int[r]);
       
        System.out.print("총 개수: ");
        System.out.println(permutation.count);
    }
}

class per{
    public int count;
        
    public per(){
        this.count = 0;
    }
        
        
    //permutation: arr에 있는 숫자들 중 r개 순열로 뽑기, arr.length의 크기를 갖고 visited를 나타내는 boolean 배열, 값을 저장하는 int배열
    public void permutation(int[] arr,int depth, int r, boolean[] visited, int[] craft){
        if(depth==r){ //depth 와 r이 같아지면 출력
            for(int i = 0; i< craft.length; i++){
                System.out.print(craft[i]);
                System.out.print(" ");
            }
            System.out.println("");
            count++;
            return;
        }
        
        for(int i = 0; i<arr.length; i++){
            if(visited[i]==false){//visite가 false이면 아직 안들어간 숫자, true이면 이미 들어간 숫자이다
                visited[i] = true;
                craft[depth] = arr[i];
                this.permutation(arr, depth+1 ,r,visited, craft);//재귀함수 들어갈때 depth+1
                visited[i] = false; //복구
                craft[depth] = 0; //복구
            }
        }
        
        
        }
}

visited 배열을 이용한 순열의 작동 순서 설명은

kkwong-guin.tistory.com/40

프로그래머스 - 소수찾기 (sol.java)

에서 자세히 설명하였다.

 

---

 

◎ 조합(combination)이란

서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다.

 

ex) [1,2,3,4]인 4개의 원소로 이루어진 배열에서, 2개의 숫자를 뽑는 경우는

(1,2)(1,3)(1,4)(2,3)(2,4)(3,4)로 6개 이다.

 

---

◎ 조합의 알고리즘적 구현 1 - 재귀를 이용한 구현

 

조합의 알고리즘에서 가장 중요한 원리는 n번째 인덱스의 숫자가 뽑혔을 경우, 뽑히지 않았을 경우 두가지로 나누는 것이다. 극단적으로 간단히 [1,2]인 2개로 이루어진 배열에서 1개의 숫자를 뽑는 경우는 (1),(2) 두가지이며,

(1)은 1이 뽑히고 2가 뽑히지 않은경우, (2)는 1이 뽑히지 않고, 2가 뽑힌 경우이다.

 

그러므로, 재귀함수가 종료(return) 되어야할 조건은

1. r개의 숫자가 뽑혔을때

2. 뽑을게 더이상 없을때

두가지 이다.

 

출처: https://minhamina.tistory.com/38

맨 위의 경우와 2번째 경우는 r개의 숫자가 뽑혔기 때문에(r==0) 재귀함수가 종료된 것이고,

3번째 경우는 0은 뽑았지만, 1과 2 모두를 뽑지 않는 경우를 탐색한 경우이므로, 더이상 뽑을게 없기 때문에(depth==0) 종료한것이다.

 

코드:

public class Main {
    
    public static void main(String[] args) {
        int arr[] = {1,2,3,4};
        int r = 2;
        //4개중 2개 뽑기
        per permutation = new per();
        permutation.permutation(arr, 0 ,r, new boolean[arr.length], new int[r]);
       
        System.out.print("총 개수: ");
        System.out.println(permutation.count);
    }
}

class per{
    public int count;
        
    public per(){
        this.count = 0;
    }
        
        
    //permutation: arr에 있는 숫자들 중 r개 순열로 뽑기, arr.length의 크기를 갖고 visited를 나타내는 boolean 배열, 값을 저장하는 int배열
    public void permutation(int[] arr,int depth, int r, boolean[] visited, int[] craft){
        if(r==0){ //숫자를 r개 뽑았으므로 재귀함수 return
            for(int i = 0; i< craft.length; i++){
                System.out.print(craft[i]);
                System.out.print(" ");
            }
            System.out.println("");
            count++;
            return;
        }
        if(depth==arr.length){ //더이상 뽑을 게 없으므로 재귀함수 return
            return;
        }
        
        visited[depth] = true; //depth번재 인덱스를 가진 숫자를 뽑은 경우
        craft[craft.length-r] = arr[depth];
        permutation(arr,depth+1,r-1,visited, craft); //다음 인덱스의 숫자 탐색 ,숫자를 뽑았으므로 r 1감소
        
        
        visited[depth] = false; //depth번재 인덱스를 가진 숫자를 뽑지 않은
        permutation(arr,depth+1,r,visited, craft); //다음 인덱스의 숫자 탐색 ,숫자를 뽑지 않았으므로 r 유지
        
        
        }
}

---

◎ 조합의 알고리즘적 구현 1 - 백트래킹을 이용한 구현 (순열 알고리즘 응용)

 

백트래킹: 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가서 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것

 

위에서 본 순열 코드는 depth가 증가될때 마다(새로운 재귀함수로 진입할 때마다), 첫 인덱스부터 다시 탐색한다.

하지만 조합에서는 새로운 재귀함수로 진입할 때마다 모든 인덱스를 다시 탐색할 필요가 없다.

[1,2,3,4] 중에 2개를 뽑는 조합의 경우의 수에서 2를 뽑았다면, 그 다음 재귀함수에서는 1은 고려하지 않고 3,4만 고려하면 된다. 왜냐하면, 1를 먼저 뽑은 경우에서 (1,2)가 경우의 수로써 이미 나와있기 때문이다. 1를 다시 고려하게 되면,

(1,2)와 중복되는 (2,1)이라는 경우의 수가 생기게된다.

 

코드:

public class Main {
    
    public static void main(String[] args) {
        int arr[] = {1,2,3,4};
        int r = 2;
        //4개중 2개 뽑기
        per permutation = new per();
        permutation.permutation(arr, 0 ,r, new boolean[arr.length], new int[r], 0);
       
        System.out.print("총 개수: ");
        System.out.println(permutation.count);
    }
}

class per{
    public int count;
        
    public per(){
        this.count = 0;
    }
        
        
    //permutation: arr에 있는 숫자들 중 r개 순열로 뽑기, arr.length의 크기를 갖고 visited를 나타내는 boolean 배열, 값을 저장하는 int배열, 백트래킹을 위한 기준점 point
    public void permutation(int[] arr,int depth, int r, boolean[] visited, int[] craft, int point){
        if(depth==r){ //depth 와 r이 같아지면 출력
            for(int i = 0; i< craft.length; i++){
                System.out.print(craft[i]);
                System.out.print(" ");
            }
            System.out.println("");
            count++;
            return;
        }
        
        for(int i = point; i<arr.length; i++){
            if(visited[i]==false){//visite가 false이면 아직 안들어간 숫자, true이면 이미 들어간 숫자이다
                visited[i] = true;
                craft[depth] = arr[i];
                this.permutation(arr, depth+1 ,r,visited, craft, i+1);//재귀함수 들어갈때 depth+1, 기준점 i+1 (0~1까지는 고려대상 x) 
                visited[i] = false; //복구
                craft[depth] = 0; //복구
            }
        }
        
        
        }
}