[Python] 순열과 조합 라이브러리 itertools

0) itertools 라이브러리

itertools에서 제공하는 클래스는 매우 다양하지만, 코딩테스트에서 가장 유용하게 사용할 수 있는 클래스는 permutations(순열)과 combinations(조합)이다.

 

- permutations(순열)은 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 계산해준다.

- combinations(조합)은 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우를 계산한다.

⇒ 두 개 모두 클래스이므로 객체 초기화 이후에는 '리스트 자료형'으로 변환하여 사용한다 !

 

1. 순열(Permutations)

from itertools import permutations

print(list(permutations([1,2,3,4], 2)))
print(list(permutations([1,2,3,1], 2)))

# result1
# [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

# result2
# [(1, 2), (1, 3), (1, 1), (2, 1), (2, 3), (2, 1), (3, 1), (3, 2), (3, 1), (1, 1), (1, 2), (1, 3)]

permutations(반복 가능한 객체, n) (n=선택할 원소 개수)

• 중복을 허용하지 않는다.
• 순서에 의미가 있다 (= 같은 값이 뽑히더라도 순서가 다르면 다른 경우의 수로 판단)

 

2. 중복 순열(product)

from itertools import product

print(list(product([1,2,3,4], repeat=2)))
print(list(product([1,2,3,1], repeat=2)))

# result1
# [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)]

# result2
# [(1, 1), (1, 2), (1, 3), (1, 1), (2, 1), (2, 2), (2, 3), (2, 1), (3, 1), (3, 2), (3, 3), (3, 1), (1, 1), (1, 2), (1, 3), (1, 1)]

product(반복 가능한 객체, repeat=num)

• 중복을 허용하는 순열

 

3. 조합(combinations)

from itertools import combinations

print(list(combinations([1,2,3,4], 2)))
print(list(combinations([1,2,3,1], 2)))

# result1
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

# result2
# [(1, 2), (1, 3), (1, 1), (2, 3), (2, 1), (3, 1)]

combinations(반복 가능한 객체, n) (n=선택할 원소 개수)

• 중복을 허용하지 않는다.
• 순서에 의미가 없다 (= 같은 값이 뽑히면 같은 경우의 수로 판단)

 

4. 중복 조합(combinations_with_replacement)

from itertools import combinations_with_replacement

print(list(combinations_with_replacement([1,2,3,4], 2)))
print(list(combinations_with_replacement([1,2,3,1], 2)))

# result1
# [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)]

# result2
# [(1, 1), (1, 2), (1, 3), (1, 1), (2, 1), (2, 2), (2, 3), (2, 1), (3, 1), (3, 2), (3, 3), (3, 1), (1, 1), (1, 2), (1, 3), (1, 1)]

combinations_with_replacement(반복 가능한 객체, n) (n=선택할 원소 개수)

• 중복을 허용하는 조합