1. 들어가며
코딩테스트를 보면 순열, 조합, 중복 순열, 중복 조합을 사용해야하는 경우가 있다.
그런데 코테를 보는 순간에 순열과 조합을 dfs 알고리즘을 사용하여 구하기에는 시간이 부족하다.
따라서 자주 사용하는 itertools 라이브러리의 순열(permutations), 조합(combinations), 중복 순열(product), 중복 조합(combinations_with_replacement)를 살펴보자.
2. 들어가기에 앞서 총정리
import itertools
A = [1, 2, 3]
def iter_test(A: list) -> None:
combination: list = list(itertools.combinations(A, 2))
permutation: list = list(itertools.permutations(A, 2))
permutation_with_repetition: list = list(itertools.product(A, repeat=2))
combination_with_repetition: list = list(itertools.combinations_with_replacement(A, 2))
print(f"list A의 값은 {A}.")
print()
print(f"A의 순열은 {permutation}")
print(f"A의 조합은 {combination}")
print(f"A의 중복 순열은 {permutation_with_repetition}")
print(f"A의 중복 조합은 {combination_with_repetition}")
iter_test(A)
list A의 값은 [1, 2, 3].
A의 순열은 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
A의 조합은 [(1, 2), (1, 3), (2, 3)]
A의 중복 순열은 [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
A의 중복 조합은 [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
3. 들어가자.
A. permutations (순열)
a. 소개
class permutations(builtins.object)
| permutations(iterable, r=None)
|
| Return successive r-length permutations of elements in the iterable.
|
| permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)
iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우 (순열)을 계산해준다.
중복 X, 순서 O
- 순열은 11!가 4000만 정도이다. 따라서 n이 10인 경우가 마지노선이다.
b. 사용 예
from itertools import permutations
data = ['a', 'b', 'c']
result = list(permutations(data, 2))
print(result)
[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]
B. combinations (조합)
a. 소개
class combinations(builtins.object)
| combinations(iterable, r)
|
| Return successive r-length combinations of elements in the iterable.
|
| combinations(range(4), 3) --> (0,1,2), (0,1,3), (0,2,3), (1,2,3)
iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우(조합)를 계산한다.
중복 X, 순서 X
- 조합은 [n=28, r=14]인 경우가 4000만 정도이다. [n=26, r=13]인 경우는 1000만 정도이다. 따라서 최악의 경우 n이 26을 넘기면 안된다.
- 이번 문제에서는 n이 26이라고 가정한다면, r이 1~26인 모든 경우를 탐색해야하므로 n이 더 낮아져야한다.
b. 사용 예
from itertools import combinations
data = ['a', 'b', 'c']
result = list(combinations(data, 2))
print(result)
[('a', 'b'), ('a', 'c'), ('b', 'c')]
C. product (중복 순열)
a. 소개
class product(builtins.object)
| product(*iterables, repeat=1) --> product object
|
| Cartesian product of input iterables. Equivalent to nested for-loops.
|
| For example, product(A, B) returns the same as: ((x,y) for x in A for y in B).
| The leftmost iterators are in the outermost for-loop, so the output tuples
| cycle in a manner similar to an odometer (with the rightmost element changing
| on every iteration).
|
| To compute the product of an iterable with itself, specify the number
| of repetitions with the optional repeat keyword argument. For example,
| product(A, repeat=4) means the same as product(A, A, A, A).
|
| product('ab', range(3)) --> ('a',0) ('a',1) ('a',2) ('b',0) ('b',1) ('b',2)
| product((0,1), (0,1), (0,1)) --> (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) ...
iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)를 계산한다. 원소를 중복하여 뽑는다.
뽑고자 하는 데이터의 수를 repeat 속성으로 넣어준다.
중복 O, 순서 O
중복 순열이라고는 했지만, 따지고 보면 데카르트 곱(Cartesian product)이다.
즉, 2개 이상의 리스트의 모든 조합을 구한다.
b. 사용 예 - 1
from itertools import product
data = ['a', 'b', 'c']
result = list(product(data, repeat=2))
print(result)
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('c', 'c')]
이 경우 data를 2개 만들어서 카테시안 곱을 구한 것이다. 따라서 중복 조합이 나온다.
c. 사용 예 - 2
from itertools import product
data = ["012", "abc", "!@#"]
result = list(product(*data)
print(result)
[('0', 'a', '!'), ('0', 'a', '@'), ('0', 'a', '#'), ('0', 'b', '!'), ('0', 'b', '@'), ('0', 'b', '#'), ('0', 'c', '!'), ('0', 'c', '@'), ('0', 'c', '#'), ('1', 'a', '!'), ('1', 'a', '@'), ('1', 'a', '#'), ('1', 'b', '!'), ('1', 'b', '@'), ('1', 'b', '#'), ('1', 'c', '!'), ('1', 'c', '@'), ('1', 'c', '#'), ('2', 'a', '!'), ('2', 'a', '@'), ('2', 'a', '#'), ('2', 'b', '!'), ('2', 'b', '@'), ('2', 'b', '#'), ('2', 'c', '!'), ('2', 'c', '@'), ('2', 'c', '#')]
D. combinations_with_replacement (중복 조합)
a. 소개
class combinations_with_replacement(builtins.object)
| combinations_with_replacement(iterable, r)
|
| Return successive r-length combinations of elements in the iterable allowing individual elements to have successive repeats.
|
| combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC"
iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우(조합)를 계산한다. 원소를 중복하여 뽑는다.
중복 O, 순서 X
b. 사용 예
from itertools import combinations_with_replacement
data = ['a', 'b', 'c']
result = list(combinations_with_replacement(data, 2))
print(result)
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')]
4. 주의할 점
itertools 라이브러리의 순열(permutations), 조합(combinations), 중복 순열(product), 중복 조합(combinations_with_replacement)는 모두 generator이다.
따라서 변수에 list타입으로 캐스팅해서 저장하지 않으면 한번의 루핑 이후 사라진다.
import itertools
A = [1, 2, 3]
def iter_test(A: list) -> None:
combination: itertools.combinations = itertools.combinations(A, 2)
permutation: itertools.permutations = itertools.permutations(A, 2)
permutation_with_repetition: itertools.product = itertools.product(A, repeat=2)
combination_with_repetition: itertools.combinations_with_replacement = itertools.combinations_with_replacement(A, 2)
print(f"list A의 값은 {A}.")
print()
print(f"A의 순열은 {list(permutation)}")
print(f"A의 조합은 {list(combination)}")
print(f"A의 중복 순열은 {list(permutation_with_repetition)}")
print(f"A의 중복 조합은 {list(combination_with_repetition)}")
print("--------------------------")
print(f"A의 순열은 {list(permutation)}")
print(f"A의 조합은 {list(combination)}")
print(f"A의 중복 순열은 {list(permutation_with_repetition)}")
print(f"A의 중복 조합은 {list(combination_with_repetition)}")
iter_test(A)
list A의 값은 [1, 2, 3].
A의 순열은 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
A의 조합은 [(1, 2), (1, 3), (2, 3)]
A의 중복 순열은 [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
A의 중복 조합은 [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
--------------------------
A의 순열은 []
A의 조합은 []
A의 중복 순열은 []
A의 중복 조합은 []
참고문헌
[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년
[2] PhireRed, Python 순열, 조합, product - itertools (velog.io). (accessed Dec 31, 2021)
Ghost