(Python) 순열, 조합 쉽게 만들기¶
결론부터 말하자면, 라이브러리에서 불러온 함수와 직접 구현한 함수가 속도차이 10배정도를 보였다. (라이브러리가 훨씬 빠름)
파이썬 documentation에서 어떻게 구현했는지 나중에 차차 확인해봐야 할 것 같다.
1. itertools를 이용하여 순열, 조합 구현하기¶
1.1 순열(=permutations)
- 반복 가능한 객체(=길이가 n인)에 대해서 중복을 허용하지 않고 r개를 뽑아서 나열한다.
- 뽑힌 순서대로 나열하기 때문에 순서가 의미가 있다.
(즉, 같은 값이 뽑히더라도 순서가 다르면 다른 경우의 수로 취급한다.)
permutations(반복 가능한 객체, r)
from itertools import permutations
for i in permutations([1,2,3,4], 2):
print(i, end=" ")
1.2 조합(=combinations)
- 반복 가능한 객체(=길이가 n인)에 대해서 중복을 허용하지 않고 r개를 뽑는다.
- 어떤 것을 뽑는지만 중요하게 보기 때문에 뽑은 순서는 고려하지 않는다.
combinations(반복 가능한 객체, r)
from itertools import combinations
for i in combinations([1,2,3,4], 2):
print(i, end=" ")
1.3 중복 순열(=product)
product(반복 가능한 객체, repeat=1)
from itertools import product
for i in product([1,2,3],'ab'):
print(i, end=" ")
for i in product(range(3), range(3), range(3)):
print(i, end=" ")
for i in product([1,2,3], repeat=2):
print(i, end=" ")
for i in product([1,2,3], repeat=3):
print(i, end=" ")
1.4 중복 조합(=combinations_with_replacement)
combinations_with_replacement(반복 가능한 객체, r)
from itertools import combinations_with_replacement
for cwr in combinations_with_replacement([1,2,3,4], 2):
print(cwr, end=" ")
2. 직접 구현하기 (itertools 사용 X)¶
직접 구현하는 부분은 네이버 블로그를 참고했다.
출처 : https://m.blog.naver.com/PostView.nhn?blogId=kmh03214&logNo=221685090465&targetKeyword=&targetRecommendationCode=1
2.1 제너레이터(=generator)를 이용한 조합
return을 이용하는 함수와 다르게, yield를 사용하는 제너레이터는 특이한 점이 있다.
return을 이용하는 함수는 어떤 인자를 받아서(물론 안받아도 되는 경우도 있다) 그 안에서 어떠한 연산을 하고 return을 하면 함수가 끝나지만, yield를 사용하는 제너레이터(=generator)는 그렇지 않다.
yield는 자신(=generator)을 호출한 객체에게 값을 던져주는?(값을 토스해준다) 역할을 할 뿐, yield를 읽었다고 해서 제너레이터(=generator)가 끝나는 것은 아니다.
제너레이터는 자신의 연산이 어디까지 진행되어있는지 기억함과 동시에 그때그때 자신을 호출하는 객체가 yield를 통해서 어떠한 값을 받길 원하는 상황에서 쓰기 매우 적절하다.
정리하자면, yield는 return과 달리 제너레이터(=generator)라는 객체를 만들어준다. return은 어떤 객체를 한번 반환하고 끝나는 역할을 한다면, yield는 제너레이터(=generator)라는 객체를 통해서 함수를 호출할 때마다 하나씩 전달해준다. 순차적으로 한번에 처리하는 것이 아니라, 함수가 호출될 때마다 순차적으로 하나씩 처리해서 값을 반환해주는 것 같다. 즉, 반복횟수 만큼 호출이 가능하다.
밑에 있는 combinations_2를 파이참을 이용해서 디버깅해봤는데 제너레이터의 동작과정을 보니 이해가 잘 되더라.
## 제너레이터를 이용해서 조합 구현 (중복 조합 X)
def combinations_2(array, r):
for i in range(len(array)):
if r == 1: # 종료 조건
yield [array[i]]
else:
for next in combinations_2(array[i+1:], r-1):
yield [array[i]] + next
print("itertools의 combinations")
for i in combinations([1,2,3,4], 3):
print(i, end=" ")
print("\n\ncombinations 직접 구현")
for i in combinations_2([1,2,3,4], 3):
print(i, end=" ")
Q1. 시간 차이는 얼마나 날까?
import time
## 일단 itertools의 조합부터 측정
print("itertools의 combinations")
start_time = time.time()
for i in combinations(range(500), 2): pass
end_time = time.time()
print(end_time - start_time)
## 직접 구현한 조합 측정
print("\n\ncombinations 직접 구현")
start_time = time.time()
for i in combinations_2(range(500), 2): pass
end_time = time.time()
print(end_time - start_time)
A1. 10배정도 시간차이가 있는 것 같다.
2.2 제너레이터(=generator)를 이용한 중복조합
중복조합은 위의 조합을 아주 조금만 바꿔주면 가능하다.
def combinations_3(array, r):
for i in range(len(array)):
if r == 1:
yield [array[i]]
else:
## array[i+1: ] -> array[i: ] 변경
for next in combinations_3(array[i:], r-1):
yield [array[i]] + next
for i in combinations_3([1,2,3,4],2):
print(i, end=" ")
2.3 제너레이터(=generator)를 이용한 순열
array[:i] + array[i+1:] 로 변경된 부분을 보면, 그 다음번에 추가시킬 원소값으로는 i번째를 포함하지 않겠다. 라고 해석할 수 있다.
하지만 이 코드의 치명적인 문제가 있는데, range가 입력값으로 들어올 경우 range는 슬라이싱이 가능하기때문에 위의 경우들은 문제가 없지만 아래의 코드는 array를 쪼개서 서로 더해주는 과정을 추가시켰기 때문에 에러가 날 수밖에 없다.
range끼리는 서로 더할 수 없기 때문이다.
문자열이나 리스트가 인수로 들어오면 문제는 없을 것 같다.
def permutations_2(array, r):
for i in range(len(array)):
if r == 1:
yield [array[i]]
else:
for next in permutations_2(array[:i]+array[i+1:], r-1):
yield [array[i]] + next
for i in permutations_2([1,2,3,4],2):
print(i, end=" ")
for i in permutations_2('abcde',2):
print(i, end=" ")
## range를 쓰면 에러가 난다.
## 앞서 말한 것 처럼, range끼리는 서로 더할 수 없기 때문이다.
for i in permutations_2(range(5),2):
print(i, end=" ")
Q2. itertools의 순열과, 제너레이터 순열의 시간차이는 얼마나 날까?
array = "abcdefghijklmnopqrstuabcdefghijklmnopqrstuabcdefghijklmnopqrstuabcdefghijklmnopqrstuabcdefghijklmnopqrstuabcdefghijklmnopqrstuabcdefghijklmnopqrstuabcdefghijklmnopqrstu"
print("itertools의 permutations")
start_time = time.time()
for i in permutations(array, 3):
pass
end_time = time.time()
print(end_time - start_time)
print("\n직접 구현한 permutations")
start_time = time.time()
for i in permutations_2(array, 3):
pass
end_time = time.time()
print(end_time - start_time)
A2.range를 사용하지 못한다는 단점도 있고, 시간차이도 10배 정도 나오는 것으로 봐서 쓸만한 구현은 아닌 것 같다. 어떻게 하면 순열을 구현할 수 있을까?
2.3.1 제너레이터(=generator)를 이용한 순열 2 (위의 순열 코드를 살짝 수정해봄)
def permutations_3(array, r, prefix="nothing"):
for i in range(len(array)):
if array[i] == prefix: continue
if r == 1:
yield [array[i]]
else:
prefix = array[i]
for next in permutations_3(array, r-1, prefix):
yield [array[i]] + next
for i in permutations_3(range(5), 2):
print(i, end=" ")
for문의 array를 쪼개서 다시 재결합하는 과정을 하지 않고, prefix를 두어서 하위의 제너레이터가 이를 이어받았을 때, prefix에 해당하는 것을 중복해서 사용하지 않도록 하는 방향으로 코드를 작성해봤다. 덕분에 range를 사용해도 에러가 뜨지 않게 되었다.
Q3.시간 차이를 비교해보자.
array = list(range(1000))
## itertools의 순열
print('itertools의 순열')
start_time = time.time()
for i in permutations(array, 2):
pass
end_time = time.time()
print(end_time - start_time)
## 처음에 만들었던 제너레이터 순열 코드 1
print('\n제너레이터 순열 1')
start_time = time.time()
for i in permutations_2(array, 2):
pass
end_time = time.time()
print(end_time - start_time)
## 두번째 만들었던 제너레이터 순열 코드 2
print('\n제너레이터 순열 2')
start_time = time.time()
for i in permutations_3(array, 2):
pass
end_time = time.time()
print(end_time - start_time)
A3.itertools의 순열이 10배정도 빠르다.
itertools의 순열과, 마지막 순열을 다시 비교해보자.
## itertools의 순열
print('itertools의 순열')
start_time = time.time()
for i in permutations(range(500), 2):
pass
end_time = time.time()
print(end_time - start_time)
## 두번째 만들었던 제너레이터 순열 코드 2
print('\n제너레이터 순열 2')
start_time = time.time()
for i in permutations_3(range(500), 2):
pass
end_time = time.time()
print(end_time - start_time)
2.4 제너레이터(=generator)를 이용한 중복 순열
def permutations_4(array, r):
for i in range(len(array)):
if r == 1:
yield [array[i]]
else:
for next in permutations_4(array, r-1):
yield [array[i]] + next
for i in permutations_4([1,2,3,4,5],3):
print(i, end=" ")
Q4. 시간 비교
## itertools의 중복 순열
print('itertools의 중복 순열')
start_time = time.time()
for i in product(range(500), repeat=2):
pass
end_time = time.time()
print(end_time - start_time)
## 제너레이터 중복 순열
print('\n제너레이터 중복 순열')
start_time = time.time()
for i in permutations_4(range(500), 2):
pass
end_time = time.time()
print(end_time - start_time)
'알고리즘 > [Python] 알고리즘' 카테고리의 다른 글
| (Python) 버블 정렬(bubble sort) (0) | 2020.02.04 |
|---|---|
| (Python) 리스트의 선형 탐색(linear search) (0) | 2020.02.04 |
| (Python) 이진 탐색(Binary Search) 구현하기 (0) | 2020.01.22 |
| (Python) 너비 우선 탐색(BFS) 구현하기 (0) | 2020.01.13 |
| (Python) 깊이 우선 탐색(DFS) 구현하기 (0) | 2020.01.10 |