JAVA로 순열, 중복 순열, 조합, 중복 조합 이해하기

프로그래머스-소수만들기문제를 해결하면서 조합코드를 찾아보게 되었고 그 외에 순열과 중복이 가능한 경우에 대해서 공부가 필요하다고 생각되서 정리해보았다.

---

🦖 순열 - Permutation

서로 다른 n개에서 r개를 뽑아서 정렬하는 경우의 수

순열에서는 순서가 중요하기 때문에 [1,2] 와 [2,1]은 순서가 다르므로 다른 경우의 수로 카운팅한다.

public class AlgorithmStudy {
    1️⃣
    public static void permutation(int[] arr, int[] out, boolean[] visited, int depth, int r){
    	2️⃣
        if(depth == r){
            for(int num: out) System.out.print(num);
            System.out.println();
            return;
        }
        3️⃣
        for(int i=0; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                out[depth] = arr[i];
                4️⃣
                permutation(arr, out, visited, depth+1, r);
                visited[i] = false;
            }
        }
    }
	5️⃣
    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], new boolean[arr.length], 0, r);
    }
}

1️⃣ permuataion은 main에서 호출된다.
	- int[] arr : 순열을 구할 배열
    - int[] out : main에서 new int[r] / 즉, 몇개씩 뽑을지
    			  순서대로 방문한 원소를 저장해야하므로 선택된 원소를 순서대로 저장할 배열 
    - boolean[] visited : 중복해서 선택하는 것은 불가능하므로 visited를 
    					이용해서 이미 선택한 원소를 다시 선택하지 않도록 함
    - int depth : r만큼 반복하기 위해서 
    - int r : 몇개씩 묶을 건지
    
2️⃣ depth의 값과 r이 같을때
	out을 반복문을 돌리면서 해당 요소를 num으로 받아서 출력해준다.
    그리고 return을 통해서 벗어난다.
    
3️⃣ i를 arr의 길이만큼 반복문을 돌린다.
	만약 visited의 i번째가 false라면 해당 i번째의 값을 true로 바꾸고
    out의 depth번째에 arr의 i번째 값을 대입한다.
    
4️⃣ depth에 +1한 값을 대입해서 permutation을 다시 호출한다.
    다시 호출 했을 때 2️⃣의 조건문을 만족하지 못하면 반복문으로 들어오는 것이고 
    만족한다면 해당 조건문을 수행한 후 다시 돌아와서 i번째 visited의 값을 false로 바꿔준다.
    
5️⃣ r과 arr의 초기값을 설정해주고 permutation을 호출한다.

결과는 ❓

1 2
1 3
2 1
2 3
3 1 
3 2

---

🦖 중복 순열

서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수

순서가 있게 뽑는 것은 순열과 동일하지만 같은 원소를 중복해서 뽑을 수 있다는 것에 차이가 있다.

public class AlgorithmStudy {
    public static void permutation(int[] arr, int[] out, int depth, int r){
        if(depth == r){
            for(int num: out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=0; i<arr.length; i++){
            out[depth] = arr[i];
            permutation(arr, out, depth+1, r);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], 0, r);
    }
}

순열 코드에서 중복을 방지하기 위해 사용했던 visited부분을 제거해주면 된다.

결과는 ❓

1 1
1 2
1 3 
2 1 
2 2
2 3 
3 1 
3 2 
3 3

---

🦖 조합 - Combination

서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

public class AlgorithmStudy {
    public static void combination(int[] arr, boolean[] visited, int start, int depth, int r){
        if(depth == r){
            for(int i=0; i<arr.length; i++){
                if(visited[i]) System.out.print(arr[i]);
            }
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                combination(arr, visited, i+1, depth+1, r);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new boolean[arr.length], 0, 0, r);
    }
}

순서가 상관이 없으니 [1,2]와 [2,1]이 같은 경우이기 때문에 [1,2]만 카운팅 해주어야한다.
그러기 위해서는 현재 선택한 원소보다 뒤에 있는 원소에 대해서만 탐색을 진행해야한다.

이를 위해서 탐색의 시작 index를 의미하는 start원소를 사용한다.
탐색의 기준을 start로 잡고 재귀호출시 현재 index인 i에 1을 더한 값을 start로 넣어준다.

visited를 이용해서 방문한 원소들을 순서대로 확인하면 곧 선택된 조합이다.

결과는 ❓

1 2 
1 3 
2 3

---

🦖 중복 조합

서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수

public class AlgorithmStudy {
    public static void combination(int[] arr, int[] out, int start, int depth, int r){
        if(depth == r){
            for(int num : out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            out[depth] = arr[i];
            combination(arr, out, i, depth+1, r);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new int[r], 0, 0, r);
    }
}

조합과의 차이점은 중복이 가능하다는 것이므로 중복을 체크하기 위해 사용한 visited를 제거해준다.

현재 선택한 원소보다 뒤의 것만 선택가능하지 않고 현재 선택한 원소를 포함한 뒤의 것들을 선택가능한 것이므로 재귀 호출에서 start로 i+1을 넘기던 조합코드를 그냥 i를 넘기는 것으로 수정해준다.

조합과 다르게 중복이 가능하므로 선택한 원소를 저장하는 배열이 필요함

결과는 ❓

1 1 
1 2
1 3
2 2 
2 3
3 3

---

📑 References

코드와 설명은 golucky.log님의 포스트를 참조