TIL 파이썬으로 조합과 순열 구하기

브루트 포스 문제를 풀던 도중 리스트에서 조합을 만들어야하는 문제들이 많아서 작성하게 되었다. 

파이썬에서 import를 하면 바로 구현 가능하지만 함수를 직접 구현하는 것이 의미가 있을 거 같아 글을 작성하였다! 

방법 1 itertools 라이브러리 이용 

조합

from itertools import combinations

arr = [0, 1, 2, 3, 4, 5]

print(list(combinations(arr, 3)))

순열 

from itertools import permutations

arr = [0, 1, 2, 3, 4, 5]

print(list(permutations(arr, 3)))

방법 2 재귀를 이용한 방법 

조합

def combinations(lst, r):
	result = []
    if r =1:
    	for i in lst:
        	result.append([i])
    else:
    	for i in range(len(lst)-r+1):
        	for j in combination(lst[i+1:], r-1):
            	result.append([lst[i]+j])
        
    return result

arr = [0, 1, 2, 3, 4, 5]

print(combinations(arr, 3))

nCr = n-1Cr-1 + n-1Cr을 이용 

lst에서 r개를 뽑는 연산을 r-1이 될 때까지 재귀함수를 이용한다 

combination([1,2,3,4],2) = ([1] + combination([2,3,4],1)) and
([2] + combination([3,4],1)) and ([3] + combination([4],1)) 을 이용한다고 생각하면 된다

순열

def perm(lst,n):
	ret = []
	if n > len(lst): return ret

	if n==1:
		for i in lst:
			ret.append([i])
	elif n>1:
		for i in range(len(lst)):
			temp = [i for i in lst]
			temp.remove(lst[i])
			for p in perm(temp,n-1):
				ret.append([lst[i]]+p)

	return ret

permutation([1,2,3,4],2) = ([1] + permutation([2,3,4],1)) and
([2] + permutation([1,3,4],1)) and ([3] + permutation([1,2,4],1)) and
([4] + permutation([1,2,3],1))

을 이용한다.

참고문헌

https://ourcstory.tistory.com/414

파이썬(Python) 리스트 모든 조합 구하기 (combination vs permutations vs product)

https://cotak.tistory.com/70

[Python] 순열, 조합 구현하기 - itertools & recursion

https://medium.com/@dltkddud4403/python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EA%B5%AC%ED%98%84-5e496e74621c

python 순열, 조합 구현