[APS] 11. Python으로 조합(Combination)만들기

1. 조합(Combination)

---

• $nCr = n-1Cr-1 + n-1Cr$

N = 5
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            print(i,j,k)

# output
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

2. 재귀를 이용해서 구현해보기!

---

def nCr(n, r, s):   # n개의 원소에서 r개를 순서없이 뽑늗다. s는 시작하는 범위
    if r == 0:
        print(*comb)
    else:
        for i in range(s, n-r+1):
            comb[r-1] = A[i]    #n-1Cr-1 (A의 i번째 원소를 선택해서 넣었다.)
            nCr(n, r-1, i+1)    #n-1Cr (i를 뽑았으므로, 다음 원소는 i+1 부터 뽑을 수 있다.)

A = [1,2,3,4,5]
n = len(A)
r = 3
comb = [0] * r
nCr(n, r, 0)

3 2 1
4 2 1
5 2 1
4 3 1
5 3 1
5 4 1
4 3 2
5 3 2
5 4 2
5 4 3

Uploaded by N2T