순열(Permutation)
(1) 값을 반환
def permutation(n,r):
def factorial(n):
if n <= 1: return 1
else: return n*factorial(n-1)
return int(factorial(n)/factorial(n-r))
# 동적 계획법(dp)을 사용하면 실행 시간을 단축할 수 있다.
(2) 순서쌍을 반환
# boj-15649
def permutation(arr, m):
used = [0 for _ in range(len(arr))]
def generate(chosen,used):
if len(chosen) == m:
for x in chosen: print(x,end=" ")
print(); return
for i in range(len(arr)):
if not(used[i]):
chosen.append(arr[i]); used[i] = 1
generate(chosen,used)
chosen.pop(); used[i] = 0
generate([],used)
n, m = map(int, input().split()); arr = []
for x in range(1,n+1): arr.append(x)
permutation(arr,m)
(3) itertools를 이용하여 구현
arr = [1,2,3,4]; r = 2
from itertools import permutations
data = list(permutations(arr, r))
print(data)
중복순열(Permutation with Repetition)
(1) 값을 반환
def permutationWithRepetition(n,r):
return pow(n,r)
(2) 순서쌍을 반환
# boj-15651
def permutationWithRepetition(arr, m):
def generate(chosen):
if len(chosen) == m:
for x in chosen: print(x,end=" ")
print(); return
for i in range(len(arr)):
chosen.append(arr[i])
generate(chosen)
chosen.pop()
generate([])
n, m = map(int, input().split()); arr = []
for x in range(1,n+1): arr.append(x)
permutationWithRepetition(arr,m)
(3) itertools를 이용하여 구현
arr = [1,2,3,4]; r = 2
from itertools import product
data = list(product(arr, repeat=r))
print(data)
조합(Combination)
(1) 값을 반환
def combination(n,r):
def factorial(n):
if n <= 1: return 1
else: return n*factorial(n-1)
return int(factorial(n)/(factorial(r)*factorial(n-r)))
# 동적 계획법(dp)을 사용하면 실행 시간을 단축할 수 있다.
(2) 순서쌍을 반환
# boj-15650
def combination(arr, m):
def generate(chosen):
if len(chosen) == m:
for x in chosen: print(x,end=" ")
print(); return
start = arr.index(chosen[-1])+1 if chosen else 0
for nxt in range(start, len(arr)):
chosen.append(arr[nxt])
generate(chosen)
chosen.pop()
generate([])
n, m = map(int, input().split()); arr = []
for x in range(1,n+1): arr.append(x)
combination(arr,m)
(3) itertools를 이용하여 구현
arr = [1,2,3,4]; r = 2
from itertools import combinations
data = list(combinations(arr,r))
print(data)
중복조합(Combination with Repetition)
(1) 값을 반환
def combinationWithRepetition(n,r):
def combination(n,r):
return int(factorial(n)/(factorial(r)*factorial(n-r)))
def factorial(n):
if n <= 1: return 1
else: return n*factorial(n-1)
return combination(n+r-1,r)
# 동적 계획법(dp)을 사용하면 실행 시간을 단축할 수 있다.
(2) 순서쌍을 반환
# boj-15652
def combinationWithRepetition(arr, m):
def generate(chosen):
if len(chosen) == m:
for x in chosen: print(x,end=" ")
print(); return
start = arr.index(chosen[-1]) if chosen else 0
for nxt in range(start, len(arr)):
chosen.append(arr[nxt])
generate(chosen)
chosen.pop()
generate([])
n, m = map(int, input().split()); arr = []
for x in range(1,n+1): arr.append(x)
combinationWithRepetition(arr,m)
(3) itertools를 이용하여 구현
arr = [1,2,3,4]; r = 2
from itertools import combinations_with_replacement
data = list(combinations_with_replacement(arr,r))
print(data)