[Python] 순열(permutation), 조합(combination) 구현

순열 (Permutation)

'''
3P2 구하기 (nPr)

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

'''

# 1. DFS를 이용
# 2. 체크리스트 이용
# 순열은 그냥 외운다.

def DFS (L):
    # 종료조건이 필요함 : r 개를 뽑으면 종료
    if L == r:
        print(list(result), end=' ')
    else:
        for i in range(len(n)):
            if checklist[i] == 0: # 0이면 뽑지 않은 것. (False)
                result[L] = n[i] # 뽑지 않았으니까 뽑고
                checklist[i] = 1 # 체크리스트에 뽑았다고 표시
                DFS (L+1)
                checklist[i] = 0 # 백트레버스 할 때 방문표시 지우기

if __name__ == "__main__":
    n = [1,2,3,4]
    r = 3

    result = [0] * r
    checklist = [0] * len(n)

    DFS(0)

 

조합(Combination)

'''
3C2

1 2
1 3
2 3

1. DFS 트리를 이용
2. 트리를 트래버스 할 때, 다음 시작점을 가지고 간다.
조합도 그냥 외운다.
'''

def DFS(L, BeginWith):
    # 종료조건
    if L == r:
        print(result)
    else:
        for i in range(BeginWith, len(n)):
            result[L] = n[i]
            DFS(L+1, i+1)
            # 이전값을 기억해야 하기 때문에 백트레버스에선 할 게 없음

if __name__ == "__main__":
    n = [1,2,3,4,5]
    r = 3

    result = [0]*r

    DFS(0, 0) # 0 level, 0 BeginWith

---

[참고] itertools 사용해서 순열, 조합 구현하기

import itertools

data = [1, 2, 3, 4, 5]

for i in itertools.permutations(data, 2):
    print(list(i), end=' ')

print()

for j in itertools.combinations(data, 2):
    print(list(j), end=' ')