파이썬 조합과 순열 사용한 문제풀이의 모든 것

목적

알고리즘 문제 풀이 시 자주 등장하는 조건은 조합과 순열을 이용한 문제 풀이이다. 이 때 레파토리 코드를 이용하여 개념을 익히고 이를 추후 적용할 수 있도록 한다. 파이썬 기본 itertools 라이브러리에서 조합과 순열을 제공하며 여러 구현 코드 방식을 알아보자.

 

 

 

조합 및 순열 - itertools, for문

조합 (combinations 함수)

- from itertool, combinations(반복 가능한 객체, r)

from itertools 입력 후, itertools.combinations(iterable, r)로 함수를 사용할 수 있다. 이 때 iterable에 있는 원소가 r 개씩 조합된다.

 

>>> import itertools
>>> number = [1,2,3,4]
>>> _combo = itertools.combinations(number,3)
>>> _combo   
<itertools.combinations object at 0x0000022BB5D48540>
>>> for i in _combo:
...     print(i)
... 
(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)

예를 들면 위와 같다. number에 대한 원소를 itertools.combinations(number,3)으로 3개씩 조합한 값을 _combo에 저장하였다. 

 

개수만 세는 경우, 아래와 같이 itertools.combinations를 통해 리턴된 iterable 값을 list로 변환한다. len() 함수를 통해 리스트 내 요소의 개수를 세면 조합의 개수를 셀 수 있다.

>>> from itertools import combinations
>>> number = [1,2,3,4]
>>> _combo = combinations(number,3)
>>> len(list(_combo))
4

 

- for문 사용

for문을 사용하여 조합을 구현할 수 있다.

>>> number = [1,2,3,4]
>>> for i in range(len(number)):
...     for j in range(i+1,len(number)):
...         for k in range(j+1,len(number)):
...             print(number[i],number[j],number[k])
...
1 2 3
1 2 4
1 3 4
2 3 4

위 i,j,k를 구성하여 3개의 숫자를 조합할 수 있다.

- i는 range(len(nums))로 nums에 있는 index를 모두 탐색 될 수 있도록 한다.

- j는 range(i+1, len(nums))로 i번째에서 선택한 값 그 다음 값을 사용한다.

-k는 range(j+1, len(nums))로 j번째에서 선택한 값 그 다음 값을 사용한다.

 

따라서 위와 같이 조합의 결과값이 정상적으로 나타나는 것을 알 수 있다.

하나 의문이 들 수 있는 부분은 예를 들어 number = [1,2,3,4]일 때 i = 3이 되는 경우일 텐데,

이 때 for i range(len(nums)):는 모든 index를 탐색하므로 당연하게도 계산되고, for j in range(i+1,len(nums)):는 i+1 = 4부터 시작이고 이는 len(nums) = 4이므로 같아 range(4,4)는 더 이상 계산되지 않고 무효 처리된다. 따라서, 인덱스를 벗어나면 무효처리되므로 해당 값은 조합에 포함되지 않는다.

 

- from itertools와 for문 계산 시간 비교

0.015와 0.03251로 itertools가 for문보다 더 빠른 성능을 보여주었다.

>>> import time
>>> import itertools
>>> start=time.time()
>>> number = [1,2,3,4,5,6,7,8,9,10,11,12]
>>> for i in itertools.combinations(number,3):
...     pass
... # print(i)
...
>>> end=time.time()
>>> print(end-start)
0.015026330947875977



>>> start_2=time.time()
>>> number = [1,2,3,4,5,6,7,8,9,10,11,12]
>>> for i in range(len(number)):
...     for j in range(i+1,len(number)):
...         for k in range(j+1,len(number)):
...             pass
...             # print(number[i],number[j],number[k])
...
>>> end_2=time.time()
>>> print(end_2-start_2)
0.032510995864868164

 

 

 

순열 (permutations 함수)

- from itertools, permutations(반복 가능한 객체, r)

>>> number = [1, 2, 3, 4]
>>> _perm = permutations(number,3)
>>> _perm
<itertools.permutations object at 0x00000217F4837630>
>>> for i in _perm:
...     print(i, end=" ")
...
(1, 2, 3) (1, 2, 4) (1, 3, 2) (1, 3, 4) (1, 4, 2) (1, 4, 3)
(2, 1, 3) (2, 1, 4) (2, 3, 1) (2, 3, 4) (2, 4, 1) (2, 4, 3)
(3, 1, 2) (3, 1, 4) (3, 2, 1) (3, 2, 4) (3, 4, 1) (3, 4, 2)
(4, 1, 2) (4, 1, 3) (4, 2, 1) (4, 2, 3) (4, 3, 1) (4, 3, 2)

가독성을 위해 결과값은 일부 줄바꿈 처리하였다. 예상한대로 조합과는 다르게 순서 상관있도록 순열 값이 출력되는 것을 알 수 있다.

 

중복 조합 (combinations_with_replacement 함수)

- from itertools, cobinations_with_replacement(반복 가능한 객체, r)

중복 조합은 조합과 마찬가지로 순서는 상관 없으며 조합과 다르게 하나의 원소를 여러 번 사용할 수 있다. (조합은 원소 사용은 1번이고, 순서는 상관이 없다.)

 

combinations_with_replacement로 구현할 수 있으며, combinations와 차이는 아래 결과로 이해할 수 있다.

#1> 조합
for i in itertools.combinations([1,2,3,4], 2):
...     print(i, end=' ')
...
(1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

#2> 중복 조합
for i in itertools.combinations_with_replacement([1,2,3,4], 2):
...     print(i, end=' ')
...
(1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

위는 #1은 조합이고, 아래 #2는 중복 조합이다. 말한 바와 같이 원소를 중복하여 사용할 수 있는 지 없는 지에 대한 차이가 있으며, itertools를 통해 구현 가능하다.

 

 

 

중복 순열 (product 함수)

- from itertools, product(반복 가능한 객체)

중복 순열은 순열과 마찬가지로 순서를 고려한다. 반복 가능한 객체끼리 각 원소별로 곱하여 값을 도출할 수 있다.

>>> from itertools import product
>>> number=[1,2,3,4]
>>> product(number)
<itertools.product object at 0x000001DE2EDAE5C0>
>>> for i in product(number, "ab"):
...     print(i, end=" ")
...
(1, 'a') (1, 'b') (2, 'a') (2, 'b') (3, 'a') (3, 'b') (4, 'a') (4, 'b')

 

repeat factor를 사용하여 원소별 곱을 쉽게 할 수 있다. 아래의 경우 number과 number끼리 곱을 만든다.

>>> from itertools import product
>>> number=[1,2,3,4]
>>> product(number)
<itertools.product object at 0x000001E1CFDCE540>
>>> for i in product(number, repeat=2):
...     print(i, end=" ")
...
(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)

 

- for문 사용

for문을 사용하여 조합을 구현할 수 있다. 조합에서의 for문과 동일하지만, i와 j와 모두 number에 대한 index를 전체 탐색한다는 것을 알 수 있다.

>>> from itertools import product
>>> number=[1,2,3,4]
>>> product(number)
<itertools.product object at 0x000001A28751E580>
>>> for i in range(len(number)):
...     for j in range(len(number)):
...         print((number[i],number[j]), end = " ")
...
(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)

 

- from itertools와 for문 계산 시간 비교

0.0180666과 0.0269959로 itertools가 for문보다 더 빠른 성능을 보여주었다.

>>> import time
>>> from itertools import product
>>> start=time.time()
>>> number=[1,2,3,4,5,6,7,8,9,10]
>>> for i in product(number, repeat=2):
...     pass
...     # print(i, end=" ")
...
>>> end=time.time()
>>> print(end-start)
0.012215137481689453
>>> start_2=time.time()
>>> number=[1,2,3,4,5,6,7,8,9,10]
>>> for i in range(len(number)):
...     for j in range(len(number)):
...         pass
...         # print((number[i],number[j]), end = " ")
...
>>> end_2=time.time()
>>> print(end_2-start_2)
0.020475149154663086

 

 

 

조합 및 순열 - yield(generator)

<참고로, yield 방식 대비 itertools이 계산이 빠른 것을 알 수 있었다.>

 

yield 함수를 사용하여 조합, 반복조합, 순열, 반복순열을 구현할 수 있다. 우선 yield 함수를 이해하기 위해서는 generator를 이해할 필요가 있다.

 

generator는 iterator를 생성해주는 함수로, 함수 안에 yield 키워드를 사용한다.

- iterable: 리스트, 튜플 등 순회 가능한 자료구조

- iterator: 값을 차례대로 반환할 수 있는 객체

- generator: iterator를 생성 해 주는 함수, 함수 안에 yield 키워드를 사용하며, yield가 있다면 generator이다.

 

def my_gen():
    yield 1
    yield 2
    yield 3

위와 같은 함수는 yield를 포함하므로 generator가 된다. 이 때 yield는 기존 사용되던 return과 다르다.

해당 함수는 함수가 실행되면 yield까지 반환하고, 멈춘다. 이 후, 다시 실행되면 다음 yield까지 실행된다. generator의 다음 값으로 넘어가는 건 next 함수를 이용한다. 아래와 같다.

 

>>> def my_gen():
...     yield 1
...     yield 2
...     yield 3
...
>>> gen=my_gen()
>>> next(gen)
1
>>> next(gen)
2
>>> next(gen)
3
>>> next(gen)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

위와 같이 next(gen)으로 generator의 다음 값을 가져 올 수 있으며, generator가 모두 소진되면 StopIteration을 표출한다.

 

 

아래에서부터는 시각적인 이해를 위해 사이트에서 함수를 돌려보는 것을 추천한다.

Python Tutor - Visualize Python, Java, JavaScript, C, C++, Ruby code execution

 

조합 - yield

재귀 함수와 yield를 통해 조합을 구현할 수 있다.

>>> def combinations(arr, r):
...     for i in range(len(arr)):
...         if r == 1:
...             yield [arr[i]]
...         else:
...             for j in combinations(arr[i+1:], r - 1):
...                 yield [arr[i]] + j
...
>>> for combi in combinations([1,2,3,4],2):
...     print(combi,end=" ")
...
[1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4]

리스트 총 원소 n개 중 r개를 뽑는 것이므로, 먼저, 하나를 선택 해 보자.

for i in range(len(arr)): arr을 전체 탐색할 수 있도록 len(arr)을 사용하고, combinations 함수가 재귀 함수이기 때문에 종료 조건은 r==1이 남았을 때로 두면 마지막으로 고르는 원소가 되어 yield 함수로 [arr[i]]을 반환한다. 반환하더라도 yield 함수이기 때문에 함수는 호출될 때 다시 계산하여 리턴한다.

 

현재까지 이 과정으로는 1명을 뽑은 것이기 때문에, r-1명을 뽑는 과정을 재귀적으로 반복한다.

다만 r-1명을 뽑을 때는 for j in combinations(arr[i+1:],r-1):을 통해 선택 함수 우측 값 중 하나를 선택한다.

선택이 완료되면 yield [arr[i]]+j를 사용하는 데, 이는 arr에서 선택된 값 더하기 r번째 선택한 값을 더한다. 이렇게 하면 리스트가 완성된다.

 

 

 

순열 - yield

>>> def permutations(prefix,k):
...     if len(prefix) == r:
...         yield prefix
...     else:
...         for i in range(k,len(arr)):
...             arr[i], arr[k] = arr[k], arr[i]
...             for next in permutations(prefix + [arr[k]], k+1):
...                 yield next
...             arr[i], arr[k] = arr[k], arr[i]
...
>>> arr = [1,2,3,4]
>>> r = 2
>>> for perm in permutations([],0):
...     print(perm, end=' ')
...
[1, 2] [1, 3] [1, 4] [2, 1] [2, 3] [2, 4] [3, 2] [3, 1] [3, 4] [4, 2] [4, 3] [4, 1] 

솔직히 이건 이해가 잘 안 돼서 외웠다. prefix라는 리스트에 개수를 추가하며, 개수가 추가 될 땐 k+1씩 더하고, k값이 r값만큼 다 차게 되면, 이를 리턴한다는 의미로 보이는 데, 구체적인 건 나중에 추가 공부를 한 후에 업데이트 하도록 해야겠다.

 

중복 조합 - yield

>>> def combinations_replacement(arr, r):
...     for i in range(len(arr)):
...         if r == 1:
...             yield [arr[i]]
...         else:
...             for j in combinations_replacement(arr[i:], r - 1):
...                 yield [arr[i]] + j
...
>>> for combi in combinations_replacement([1,2,3,4],2):
...     print(combi,end=" ")
...
[1, 1] [1, 2] [1, 3] [1, 4] [2, 2] [2, 3] [2, 4] [3, 3] [3, 4] [4, 4] 

중복 조합은 for j in combinations_replacement(arr[i+1:], r-1):이 아닌 for j in combinations_replacement(arr[i], r-1):이 되어 자기 자신도 선택될 수 있도록 구성된다. 따라서, 원소의 중복을 허용하므로 중복 조합이 선택된다.

 

중복 순열 - yield

>>> def combinations(arr, r):
...     for i in range(len(arr)):
...         if r == 1:
...             yield [arr[i]]
...         else:
...             for j in combinations(arr, r - 1):
...                 yield [arr[i]] + j
...
>>> for combi in combinations([1,2,3,4],2):
...     print(combi,end=" ")
...
[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]

위 조합에서 크게 달라진 것은 없고, for j in combiations(arr[i+1:],r-1):에서 for j in combiations(arr,r-1):로 변경되었다. arr에 대해서 모두 완전 탐색하겠다는 의미이다. 따라서 원소의 중복을 허용하고 각 리스트가 선택하고자 하는 요소 개수만큼 완전 탐색되므로 중복 순열이 된다.

 

Reference

조합 / 중복조합 / 중복순열 알고리즘 - Python 매우간단!(itertools사용x) : 네이버 블로그 (naver.com)