조합, 순열 구현하기

python에서 조합, 순열을 구현하는 방법을 정리해봤다.

💡 조합

📌 서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합
iterable한 객체에 대해서 중복을 허용하지 않고 r개를 뽑는다.
단, 뽑은 순서는 고려하지 않는다.

• 구현

from itertools import combinations
a = [1, 2, 3]
print(list(combinations(a, 2)))

# 출력 : [(1, 2), (1, 3), (2, 3)]

• 직접 구현

def comb(population,num):
	ans = []
    ## 정의된 값인지 확인한다.
	if num > len(population): return ans
	## Base Case
	if num == 1:
		for i in population:
			ans.append([i])
    ## General Case
	elif num>1:
		for i in range(len(population)-num+1): ## i가 시작하는 값 - len(population) - (n-1)이고 이 때 n은 lst로부터 추출할 개수와 같다.
			for temp in comb(population[i+1:],num-1):
				ans.append([population[i]]+temp)

	return ans

💡 중복 조합

📌 n개인 것 중에서 r개 취하는 조합에서 중복을 취하는 것
nHr=n+r−1Cr

💡 순열

📌 서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수.
iterable한 객체에 대해서 중복을 허용하지 않고 r개를 뽑아 나열한다.
뽑힌 순서대로 나열하기 때문에 순서가 의미있다.
즉, (1, 2)와 (2, 1)은 다른 경우의 수다.

• 구현

from itertools import permutations
a = [1, 2, 3]
print(list(permutations(a, 2)))

# 출력 : [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

💡 중복 순열

• 구현

from itertools import product
a = [1, 2, 3]
print(list(product(a, repeat=2)))
# 출력 : [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

Reference

• 조합
• 순열
• https://juhee-maeng.tistory.com/91
• https://learnandearn.tistory.com/21