Combination 조합

- n개의 원소에서 r 개의 원소를 순서에 상관없이 뽑는 경우의 수 
- nCr = n! / (n-r)! * r!
- nCr = n-1Cr-1 + n-1Cr

 

---

 

조합? 

조합은 n 개의 원소 중에서 순서를 고려하지 않고 원하는 개수만큼 뽑는 경우의 수를 말합니다.

순서를 고려해서 뽑는 순열에서 중복을 제거해준 형태로 볼 수 있죠. 따라서 순열에서 r! 만큼 더 나눠준 형태를 띕니다.

nCr
= nPr / r!  
= n! / (n-r)! * r!

조합에는 기억해야 할 중요한 성질이 있습니다. 결론부터 보면,

nCr = n-1Cr-1 + n-1Cr 

의 공식인데요, 이 의미를 살펴보면,
하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우를 나타냅니다.

예를 들어, [1, 2, 3] 에서 2개를 뽑는 경우의 수는
3을 미리 뽑아두고 나머지 [1, 2] 중에서 1개를 뽑는 경우와
3을 뽑지 않고 나머지 [1, 2] 중에서 2개를 뽑는 경우의 합으로 볼 수 있습니다.

[1, 2, 3] 에서 2개를 뽑는 조합은
[1, 2]
[1, 3]
[2, 3]
로 총 3가지죠.

여기서 3을 뽑을 미리 뽑아둘 경우 [1, 2] 중 1개를 선택하는 경우는 2개
3을 뽑지 않을 경우에 [1, 2] 중 2개를 모두 뽑아야 하므로 1개가 됩니다.

이 성질을 이용해서 재귀적으로 구현하면 쉽게 구현할 수 있습니다 :)

구현

경우의 수

먼저 경우의 수를 구하는 방법을 구해보겠습니다.

5개 중에서 3개를 뽑는 경우를 구하고자 한다면,
5Cr 이 되고 이는 4C2 + 4C3 의 합이 됩니다. 딱 봐도 재귀 써주세요 하고있죠??

뽑아야 할 개수 r 이 0이 되면 더 이상 선택의 여지가 없으므로 1을 리턴합니다. (sholudSelect == 0)
전체 개수가 뽑아야 할 개수와 같다면 역시 다 뽑는 것 말고는 선택의 여지가 없으므로 1을 리턴합니다. (total == should)

func combination(_ total: Int, _ shouldSelect: Int) -> Int {
    if total == shouldSelect || shouldSelect == 0 {
        return 1
    } else {
        return combination(total-1, shouldSelect) + combination(total-1, shouldSelect-1)
    }
}

combination(5, 3) // 10

 

조합 구하기

참 간단하죠? 이제 이걸 조금 응용해서 진짜 조합을 구해보겠습니다.

아이디어는 배열의 인덱스를 증가시켜가면서 해당 인덱스를 뽑을지 안 뽑을지를 결정해서 조합을 만들어 나가는 것입니다.
종료 조건은 인덱스가 배열의 끝에 도달했을 때(조합을 만들 수 없음), 만든 조합이 뽑아야 할 개수를 다 뽑았을 때(조합 완성) 입니다.

func combination(total: [Int], shouldSelect: Int, current index: Int, selected: [Int]) {
    if shouldSelect == 0 {
        print(selected)
    } else if index == total.count {
        return
    } else {
        var newSelected = selected
        newSelected.append(total[index])
        combination(total: total, shouldSelect: shouldSelect-1, current: index+1, selected: newSelected)
        combination(total: total, shouldSelect: shouldSelect, current: index+1, selected: selected)
    }
}

combination(total: [1,2,3,4,5], shouldSelect: 3, current: 0, selected: [])
/*
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
*/

 

이상 조합에 대해 알아봤습니다! 순열조합, 정리하고 나면 별 것 아니지만 제대로 이해하고 있지 못하면 항상 헷갈리고 어렵게 다가오는 녀석들이죠! 이번에 확실히 잡고 갑시다 :)

감사합니다!