[알고리즘] 수열의 순열과 조합

순열(${}_n{\mathrm{P}}_k$)과 조합(${}_n{\mathrm{C}}_k$)

---

특정 수열에 대해 순열과 조합을 구하는 방법을 알아보자.

 

먼저 순열은 Permutation의 앞 글자를 따서 ${}_n{\mathrm{P}}_k$로 나타내고, n개의 수열에서 r개의 수를 뽑아 정렬하는 가짓수이다.

예를 들어, { 1, 2, 3 }이란 수열이 있고, ${}_3{\mathrm{P}}_2$를 구해보면 다음과 같다.

 

{1, 2}, {2, 1}, {1, 3}, {3, 1}, {2, 3}, {3, 2}      <--------  총 6개

 

순열은 정렬이 의미가 있기 때문에 {1, 2}와 {2, 1}은 구분된다.

 

다음으로 조합은 Combination의 앞 글자를 따서 ${}_n{\mathrm{C}}_k$로 나타내고, n개의 수열에서 r개를 뽑는 가짓수이다.

{ 1, 2, 3 } 수열에서 ${}_3{\mathrm{C}}_2$를 구해보면 다음과 같다.

 

{1, 2}, {1, 3}, {2, 3}         <-------- 총 3개

 

조합은 정렬이 의미가 없기 때문에 {1, 2}와 {2, 1}은 같은 걸로 취급된다.

 

 

 

코드

---

먼저 조합을 구하는 코드를 살펴보자.

public class Combination {
    
    public static void main(String[] args) {
        int[] arr = { 1, 3, 5, 7, 9 };
        int n = arr.length, r = 3;
        int[] combArr = new int[n];
 
        doCombination(combArr, n, r, 0, 0, arr);
    }
 
    private void doCombination(int[] combArr, int n, int r, int index, int target, int[] arr) {
        if (r == 0) {
            for (int i = 0; i < index; i++) 
                System.out.print(arr[combArr[i]] + " ");
            System.out.println();
        } else if (target == n) return;
        else {
            combArr[index] = target;
            doCombination(combArr, n, r - 1, index + 1, target + 1, arr); // (i)
            doCombination(combArr, n, r, index, target + 1, arr);         // (ii)
        }
    }
}

 

 

 

참고자료

---

[1] https://onsil-thegreenhouse.github.io/programming/algorithm/2018/04/05/permutation_combination/