알고리즘 2: 조합 & 순열

조합(Combination)

조합은 n개의 index 중 0~n, 1~n, 2~n ... 순으로 append 하며, 고른 요소의 수(level)가 r에 도달하면 return하는 방식

example: 5C3

[1,]                                                           	
	[1,2,]
    	[1,2,3], [1,2,4], [1,2,5] 
    [1,3,]
    	[1,3,4], [1,3,5]
    [1,4,]
    	[1,4,5]
[2,]
	[2,3,]
    	[2,3,4], [2,3,5]
    [2,4,]
    	[2,4,5]
[3,]
	[3,4,]
    	[3,4,5]
        

-> index의 시작점을 1씩 늘리는 재귀적 구조로 구현 가능.

# lst의 요소를 nCr
N = 5
R = 3
choose = []
lst = [1,2,3,4,5]

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

순열(Permutation)

순열의 경우 순서가 있다는 특성에 의해, index를 매번 0~n 순으로 append 하며 고른 요소의 수(level)가 r에 도달하면 return. 단, 중복을 피하기 위한 check 리스트가 필요하다.

example: 5P3

[1,]                                                           	
	[1,2,]
    	[1,2,3], [1,2,4], [1,2,5] 
    [1,3,]
    	[1,3,2], [1,3,4], [1,3,5]
    [1,4,]
    	[1,4,2], [1,4,3], [1,4,5]
    [1,5,]
    	[1,5,2], [1,5,3], [1,5,4]
[2,]
	[2,1,]
    	[2,1,3], [2,1,4], [2,1,5]
    [2,3,]
    	[2,3,1], [2,3,4], [2,3,5]
    [2,4,]
    	[2,4,1], [2,4,3], [2,4,5]
    [2,5,]
    	[2,5,1], [2,5,3], [2,5,4]
[3,]
	[3,1,]
    	[3,1,2], [3,1,4], [3,1,5]
    [3,2,]
    	[3,2,1], [3,2,4], [3,2,5]
    [3,4,]
    	[3,4,1], [3,4,2], [3,4,5]
    [3,5,]
    	[3,5,1], [3,5,2], [3,5,4]
[4,]
	[4,1,]
    	[4,1,2], [4,1,3], [4,1,5]
    [4,2,]
    	[4,2,1], [4,2,3], [4,2,5]
    [4,3,]
    	[4,3,1], [4,3,2], [4,3,5]
    [4,5,]
    	[4,5,1], [4,5,2], [4,5,3]
[5,]
	[5,1,]
    	[5,1,2], [5,1,3], [5,1,4]
    [5,2,]
    	[5,2,1], [5,2,3], [5,2,4]
    [5,3,]
    	[5,3,1], [5,3,2], [5,3,4]
    [5,4,]
    	[5,4,1], [5,4,2], [5,4,3]
        

# lst의 요소를 nPr
N = 5
R = 3
choose = []
check = [False] * N
lst = [1,2,3,4,5]

def permutation(level):	# 매 요소에서 0~N까지 
    global N, R, choose, lst
    if level == R:
        print(choose)
        return
    for i in range(N):
    	if check[i] == True:	# 중복된 요소라면 append 하지 않음
        	continue
        choose.append(lst[i])
        check[i] = True		# 중복 표기
        permutation(level+1)
        check[i] = False	# 중복 해제
        choose.pop()
        
permutation(0)

중복조합, 중복순열

중복순열(nπr)의 경우 permutation 구현에서 중복요소 check만 빠지면 된다!

# lst의 요소를 nπr
N = 5
R = 3
choose = []
lst = [1,2,3,4,5]

def product(level):
    global N, R, choose, lst
    if level == R:
        print(choose)
        return
    for i in range(N):
        choose.append(lst[i])
        product(level+1)
        choose.pop()
        
permutation(0)

중복조합 nHr = n+r-1Cr = n+r-1Cn-1 로 변경해서 푼다!
(고등수학 수준의 중복조합 설명: https://blog.naver.com/baboedition/220933436576)

로또

-> r = 6인 전형적인 조합문제

def comb(index, level):
    global choose, lst, k
    if level == 6:
        print(' '.join(choose))
        return
    for i in range(index, k):
        choose.append(lst[i])
        comb(i+1, level+1)
        choose.pop()

while True:
    case = input().split()
    if len(case) == 1:
        break
    k = int(case[0])
    choose = []
    lst = case[1:]
    comb(0,0)
    print()

암호 만들기

-> 조건이 주어진 조합 또는 순열의 문제는 조건부를 따로 함수로 구현해두는 것이 좋다.
-> 조합 또는 순열을 만드는 알고리즘은 n개의 요소를 index 순으로 삽입하기 때문에, 문제에 '사전 순으로 출력' 등의 조건이 붙은 경우 반드시 처음부터 n개의 입력 요소를 정렬하고 시작하는 것이 좋다.

L, C = tuple(map(int,input().split()))
chars = sorted(input().split())
mo_chars = ['a', 'e', 'i', 'o', 'u']
choose = []

def is_possible(choose:list):
    mo = 0
    for char in choose:
        if char in mo_chars:
            mo += 1
    ja = len(choose) - mo
    return (mo >= 1 and ja >= 2)

def com(index, level):
    global L, C, chars, choose
    if level == L:
        if is_possible(choose):
            print(''.join(choose))
        else:
            pass
    for i in range(index, C):
        choose.append(chars[i])
        com(i+1, level+1)
        choose.pop()
        
com(0,0)

(+) 틀린 풀이: 가능한 조합을 모두 만들어놓은 다음, 조건에 맞지 않는 조합을 삭제하는 방식
-> list를 순회하면서 요소를 제거하면, 순회 도중 list의 indexing이 변경되면서 버그가 발생하므로 오답이 됨! 이러한 논리로 문제를 풀려면 조건에 맞는 것을 다른 list에 하나씩 추가하는 식으로 진행되어야 함.
-> 문자열 각각을 오름차순으로, 문자열들끼리도 오름차순(사전순)으로 정렬하기 위해 sorted()를 두번 사용하는 것 보다는 초기 input부터 정렬시키는 것이 훨씬 효율적.

from itertools import combinations

L, C = input().split()
chars = list(input().split())

mo = ['a', 'e', 'i', 'o', 'u']

candidates = list(combinations(chars, int(L)))
for can in candidates:
    mo_num, ja_num = 0, 0
    for i in can:
        if i in mo:
            mo_num += 1
        else:
            ja_num += 1
    if mo_num < 1 or ja_num < 2:
        candidates.remove(can)	# candidates의 요소를 직접 삭제하면서 indexing에 문제가 발생함.
sol = []       
for ans in candidates:
    ans_str = ''
    for i in sorted(ans):
        ans_str += i
    sol.append(ans_str)

for i in sorted(sol):	# sorted를 두번 중복으로 사용 -> 비효율
    print(i)

-> 수정된 풀이

from itertools import combinations

L, C = map(int, input().split())
chars = input().split()

mo = {'a', 'e', 'i', 'o', 'u'}

candidates = list(combinations(sorted(chars), L))	# 초기값 chars를 처음부터 정렬
valid_candidates = []

for can in candidates:
    mo_num, ja_num = 0, 0
    for i in can:
        if i in mo:
            mo_num += 1
        else:
            ja_num += 1
    if mo_num >= 1 and ja_num >= 2:
        valid_candidates.append(''.join(can))	
        # candidates의 요소를 삭제하는 것이 아니라 조건에 맞는 요소를 valid_candidates에 보관

for ans in valid_candidates:
    print(ans)