[파이썬] permutation, combination 순열과 조합

순열(순서의 나열)

- 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수

- 순서상관 o -> (A, B)와 (B, A)는 다른 것

- Permutation

import itertools

arr = ['A', 'B', 'C']
per = itertools.permutations(arr, 2)
print(list(per))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

DFS 방식을 사용해서 순열을 구할 수도 있다

def _DFS(L):
    global cnt
    if L==m:
        for j in range(L):
            print(res[j],end=' ')
        print()
        cnt+=1
    else:
        for i in range(1,n+1):
            if ch[i]==0:
                ch[i]=1
                res[L]=i
                _DFS(L+1)
                ch[i]=0
                
n,m=3,2
res=[0]*n
ch=[0]*(n+1)
cnt=0
_DFS(0)
print(cnt)

조합

- 서로 다른 n개 중에서 r개를 선택

- 순서고려x -> (A, B)와 (B, A)는 같은 것으로 취급

import itertools

arr = ['A', 'B', 'C']
com = itertools.combinations(arr, 2)
print(list(com))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'C')]

DFS 방식을 사용한 조합 구현

def DFS(L,s):
    global cnt
    if L==m:
        for j in range(L):
            print(res[j],end=' ')
        cnt+=1
        print()
    else:
        for i in range(s,n+1):
            res[L]=i
            DFS(L+1,i+1)

n,m=4,2
res=[0]*(n+1)
cnt=0
DFS(0,1)
print(cnt)

 

순열과 조합은 튜플형태이기 때문에 경우에 따라 리스트로 변환하여 사용해도 된다