조합 알고리즘 복습

N = 10 
R = 5 
lst = [1,2,3,4,5,6,7,8,9,10]

choose = [] 

def combination(index, level): 
	if level ==5: 
    	print(choose)
        return 
    #
    for i in range(index, N): 
    	choose.append(lst[i])
        combination(i+1, level+1)
        choose.pop()
combination(0,0)

6603번 풀이
문제 설명

• k개의 수 중 6를 뽑는 경우의 수를 모두 출력
• 입력은 오름 차순, 출력은 사전순

입력예)

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

출력예)
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
...

방법 1. recursive

#일단 입력 먼저 받기 
#공백으로 되어 있는 str 

def combinations(index, level): 
	global choose, arr, k 
	if level ==6: 
		#print(choose) # array가 출력 
		for u in choose: 
			print(u, end = ' ')
		print()
		return 

	for i in range(index, k): 
		choose.append(arr[i])
		combinations(i+1, level+1)
		choose.pop()



while True: 
	choose = []
	n = list(map(int, input().split()))
	k = n[0]

	arr = n[1:]

	if k ==0: 
		break 
	combinations(0,0)
	print()

방법 2. itertool 쓰기

from itertools import combinations 

while TrueL 
	I = list(map(int, input().split)))
    k = I[0]
    arr = I[1:] 
    if k ==0: 
    	break 
    #반복 
    for comb in combinators(arr, 6): 
    	for u in comb: 
        	print(u, end = ' ') 
        print() 
    print() 
    

알아두면 좋을 내용

• list(map(int, input().split()))의 의미: 입력이 공백을 포함한 숫자로 되어있다면 리스트 형태로 저장하는 것
• 파이썬의 combinations

from itertools import combinations 

lst = [1,2,3,4] 
print(list(combinations(lst, 2))) # 리스트안에 저장함. 

• 조합 공식 계산하는 법
  - nCr