파이썬으로 순열과 조합 구현

문제를 먼저 풀어보고 강의를 듣는편인데 순열을 나열하는 문제가 나왔다. 고민해서 풀었는데 다 풀고 강의를 보니 그냥 itertools를 import 해서 해결했다.

순열(permutation)

$n$개에서 $r$개를 택하여 나열하는 경우의 수 이다.
예를 들어 1~3까지의 수에서 2개를 선택하여 나열하는 경우는 아래와 같이 6개 이다.

[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]

파이썬으로 순열의 출력을 구현

순열의 경우의 수는 $\frac{n!}{(n-r)!}$ 이기 때문에 아래와 같이 팩토리얼을 구현 하듯이 재귀함수를 이용하여 구현이 가능하다.

def permutation(n, r, p=[]):
	if r == 0:
    	print(p)
    else:
    	for i in range(1, 1+n):
        	if p.count(i) == 0:
            	p.append(i)
                permutation(n, r-1, p)
                p.remove(i)

$r$이 0인 경우는 출력하고 그 이외의 경우에는 리스트에 숫자를 추가한 후 다시 permutation 함수를 호출 하면 된다. 그 후, 앞서 선택했던 숫자를 제거한다.

[] -> [1] -> [1, 2] -> print -> [1] -> [1, 3] -> print -> [1] -> [] -> [2] 
-> [2, 1] -> print -> [2] -> [2, 3] -> print -> ...

조합(combination)

$n$개에서 $r$개를 택하는 경우의 수 이다. 위 순열이랑 차이점은 나열을 하지 않아도 되기 때문에 선택하는 순서가 상관 없다는 점이다.
예를 들자면, 1~3까지의 수에서 2개를 선택하는 경우는 3가지 이다.

[1, 2], [1, 3], [2, 3]

파이썬으로 조합의 출력을 구현

조합의 경우 순서가 상관없기 때문에 위에서 구현한 순열 함수에서 순서가 역순인 경우, (예를 들면 $[2, 1]$) 를 출력하지 않아도 된다. 즉, 앞서 리스트에 추가한 숫자보다 큰 경우만 추가하면 된다.

def combination(n, r, c=[]):
	if r == 0:
    	print(c)
    else:
    	for i in range(1, 1+n):
        	if c.count(i) == 0 or i > max(c):
            	c.append(i)
                combination(n, r-1, c)
                c.remove(i)

수행되는 과정을 나열해보면,

[] -> [1] -> [1, 2] -> print -> [1] -> [1, 3] -> print -> [1] -> [] -> [2] 
-> [2, 3] -> print -> [2] -> [3] -> 종료

itertools

위 함수들 말고 강의에서 나온 itertools 를 이용하여 출력 할 수 도 있다. 조합만 해보자면, 아래와 같이 매우 간단하게 출력할 수 있다.

from itertools import combinations

print(list(combinations(range(3), 2)))

결과>

[(0, 1), (0, 2), (1, 2)]

레퍼런스(Referance)

doc.python.org - itertools - combinations