[Algo] 조합 만들기

조합

서로 다른 n개의 원소에서 r개를 중복없이 순서에도 상관없이 선택하는 것을 조합(combination)이라고 한다.

(1) 백트래킹을 이용한 Hard Coding

# 이 3중 포문을 토대로 재귀함수 작성해보기
for i in range(0,N-2):
	for j in range(i+1,N-1):
		for k in range(j+1,N):
			print(arr[i],arr[j],arr[k])

#=====================================
def comb(start,stop):
	if stop == 0:
		return

	for i in range(start, N - stop + 1):
		pick.append(arr[i])
		comb(i + 1,stop - 1)
		pick.pop()

arr = 'ABCDE'
pick = []
N = len(arr)
comb(0,3)

(2) 모듈사용

from itertools import combinations

arr = [1,2,3,4,5]
arr = list(combinations(arr,3))
print(arr)
#==================================
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), 
(1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]

------------------------------------
for lst in arr:
    print(lst)
#==================================
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)