[Python] 재귀로 순열, 조합

• 순열 재귀로 표현

def f(m,n,k): # 순열 p[m]을 채우는 함수, n개 중 k개 고르기
    global cnt
    if m == k:
        cnt += 1
        print(p)
    else:
        for i in range(n): # used에서 사용하지 않은 숫자 검색
            if used[i] == 0: # 앞에서 사용하지 않은 숫자인 경우
                used[i] = 1 # 사용함으로 표시
                p[m] = a[i] # p[m] 결정
                f(m+1,n,k)
                used[i] = 0 # a[i]를 다른 위치에서 사용할 수 있도록 함
    return

a = [1,2,3,4,5]
p = [0]*3
used = [0]*len(a)
cnt = 0
f(0,5,3) # 5P3
print(cnt) # 60

 

• 조합 재귀로 표현 - 1

def nCr(n,r,s): # n개에서 r개를 고르는 조합, s선택할 수 있는 구간의 시작
    global cnt
    if r == 0:
        cnt += 1
        print(comb)
    else:
        for i in range(s,n-r+1):
            comb[r-1] = A[i]
            nCr(n,r-1,i+1)
n = 5
r = 3
comb = [0]*r
A = [i for i in range(1,n+1)]
cnt = 0
nCr(n,r,0)
print(cnt) # 10

 

• 조합 재귀로 표현 - 2 (크기 순서대로 나열)

# # n개에서 r개를 고르는 조합, s선택할 수 있는 구간의 시작, k 고른 개수
def nCr2(n,r,s,k):
    if k == r:
        print(comb2)
    else:
        for i in range(s,n-r+k+1): # n-r+k 선택할 수 있는 구간의 끝
            comb2[k] = A2[i]
            nCr2(n,r,i+1,k+1)

n2 = 5
r2 = 3
A2 = [i for i in range(1,n2+1)]
comb2 = [0]*r2
nCr2(n2,r2,0,0)

 

 

 

• 조합 반복으로 표현 (크기가 정해져 있어야 함)

# 5개 중 3개 뽑기
for i in range(0,3): # j,k로 선택될 원소를 남김
    for j in range(i+1,4): # k로 선택될 원소를 남김
        for k in range(j+1,5):
            print(i,j,k)