순열이란 서로 다른 n개 중 r개를 골라 순서를 고려해 나열하는 가짓수를 말한다. nPr
로 표시한다. 사실 순열은 itertools
를 이용하면 쉽게 구현할 수 있다. 하지만 재귀로 직접 구현하는 방법을 알아보고자 한다. (itertools를 사용하여 구현하는 방법은 포스팅 마지막에 남기겠다.)
# 중복 순열
# 주사위를 N번 던졌을 때 모든 경로 출력
dice = [1,2,3,4,5,6] # br
N = int(input())
path = [0]*N
def abc(level):
if level == N: # N까지 뽑았으면 스탑
print(*path, end = '\n')
return
for i in range(6): # 주사위 숫자 종류
path[level] = dice[i]
abc(level+1)
abc(0)
# A,B,C,D중에서 금,은,동메달 받을 사람 뽑는 경우의수
arr = ['A','B','C','D'] # br
path = [0]*3
used = [0]*4 # br의 개수 만큼 만들기, 중복 방지위해 만듦
def abc(level):
if level == 3:
print(*path)
return
for i in range(4):
if used[i] == 0: # 중복 방지
path[level]=arr[i]
used[i] = 1
abc(level+1)
used[i] = 0 # 재귀 탈출하면 돌려줌
abc(0)
# 배열 하나로 순열 만드는 법
p = list('ABCDE')
def perm(n, k): # n: 선택된 원소의 개수, k: 총 원소의 개수
if n == k: # 배치가 다 되었을 때 print
print(p)
return
for i in range(n, k): # index n앞의 숫자들을 이미 배치된 숫자, 그러므로 index n뒤의 숫자들과 자리를 바꿔가며 배치해야 함
p[n], p[i] = p[i], p[n]
perm(n+1, k)
p[n], p[i] = p[i], p[n] # 원상복구
perm(0, 5)
완전 탐색 알고리즘에서 불필요한 분기(Branch) 를 가지치기(Pruning) 하는 것이다. 정답을 도출하기 전 탐색 과정 중에 정답이 될 수 없는 조건에 해당된다면 제외하여 효율을 높일 수 있다.
순열을 구하는 과정에서도 정답에 특정 조건이 붙어 모든 경우의 수를 구하는 경우가 아닐 때 백트래킹(Backtracking)을 이용해 효율을 높일 수 있다.
candidates=['A','B','C','D']
path=['']*3
def abc(level):
if level==1 and path[level-1]=='C': return # 진입 후에 제외
if level==3:
print(*path)
return
for i in range(4):
#if level==0 and candidates[i]=='C': continue # 진입 전에 제외
path[level]=candidates[i]
abc(level+1)
abc(0)
candidates=['A','B','C','D']
path=['']*3
def abc(level):
#if level > 0 and path[level-1]=='B': return # B 진입 후에 제외
if level == 3:
print(*path)
return
for i in range(4):
if i==1: continue # B 진입 전에 제외
path[level]=candidates[i]
abc(level+1)
abc(0)
candidates=['A','B','C','D']
path=['']*3
def abc(level):
# if level > 1 and path[level-1] == path[level-2]: return # 진입 후에 제외
if level==3:
print(*path)
return
for i in range(4):
if level > 0 and (path[level-1] == candidates[i]):continue # 진입 전에 제외
path[level]=candidates[i]
abc(level+1)
abc(0)
itertools
를 이용하여 순열과 조합을 구현하면, 직접 구현한 것보다 시간이 10배 정도 덜 걸린다.
import itertools
arr = ['A', 'B', 'C']
result = itertools.permutations(arr, 2) # 반복 가능한 객체, r = 뽑는 개수
print(list(result))
# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
from itertools import product
arr = ['A', 'B', 'C']
result = product(arr, arr, [1, 2]) # 반복 가능한 객체, 반복 가능한 객체, ..
print(list(result))
# [('A', 'A', 1), ('A', 'A', 2), ('A', 'B', 1), ('A', 'B', 2), ('A', 'C', 1), ('A', 'C', 2), ('B', 'A', 1), ('B', 'A', 2), ('B', 'B', 1), ('B', 'B', 2), ('B', 'C', 1), ('B', 'C', 2), ('C', 'A', 1), ('C', 'A', 2), ('C', 'B', 1), ('C', 'B', 2), ('C', 'C', 1), ('C', 'C', 2)]
from itertools import product
result = product([1,2,3], repeat=2) # 반복 가능한 객체, repeat=n (n번 반복)
print(list(result))
# [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
import itertools
arr = ['A', 'B', 'C']
result = itertools.combinations(arr, 2) # 반복 가능한 객체, r = 뽑는 개수
print(list(result))
# [('A', 'B'), ('A', 'C'), ('B', 'C')]
from itertools import combinations_with_replacement
arr = ['A', 'B', 'C', 'D']
result = combinations_with_replacement(arr, 2) # 반복 가능한 객체, r = 뽑는 개수
print(list(result))
# [('A', 'A'), ('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'C'), ('C', 'D'), ('D', 'D')]