사실 이 포스팅은 순열을 만드는 방법에 대한 매우 비효율적인 접근에 대한 글입니다. 효율적인 순열/조합 생성 코드는 이 글을 참고하세요.
순열을 만드는 가장 간단한 방법으로는 특정 원소를 하나씩 뺀 후 배열의 나머지를 순열한 각 결과에 빼냈던 원소를 앞에 붙여준 결과를 모으는 방법이 있다. 대략의 코드는 다음과 같다.
def rec_perm(iterable):
if len(iterable) == 1:
return [list(iterable)]
result = []
for i in range(len(iterable)):
head = iterable[i]
tail = iterable[:i] + iterable[i+1:]
result += [[head] + x for x in rec_perm(tail)]
return result
이 알고리듬의 가장 큰 문제는 한 번에 모든 순열을 다 생성해서 그 리스트를 만환한다는 말이다. 만약 원소가 100개라면?1 메모리 부족으로 컴퓨터가 뻗을 수 있다. 물론 10개 미만의 연속열에 대해서는 나름 나쁘지 않은 성능을 낼 수 있다.
이를 좀 개선하여 재귀를 사용하지 않는 제너레이터 함수를 작성할 수 있는지 살펴보자. 즉 모든 순열을 미리 다 구하지 않고 Lazy하게 한 번에 하나씩 다음 순열을 만들 수 있는지를 살펴보는 것이다.
(물론 누가 먼저 고안해낸 방법일 수 있지만) 내가 생각한 방법은 원소들을 임의로 자리바꿈하지 않고, 원소들의 인덱스 집합을 조작하여 순서가 변경된 인덱스 리스트를 만들고 그 위치대로 리스트를 재배치하는 것이다.
먼저 준비할 것들이다.
- 시퀀스 크기와 동일하게 인덱스 정보를 담는 리스트 indices를 생성한다. 이는 0~n-1 까지의 정수가 들어간다.
- head, tail의 리스트를 준비한다. head는 빈 리스트이고, tail은 indices와 동일하다. 이 두 리스트는 인덱스 숫자들을 나눠 담는다.
- 인덱스들은 tail 과 head를 오가면서 자리를 바꾼다. 이 과정은 여러 depth에 걸쳐 일어나므로 그 과정에서 인덱스의 위치를 기억해둘 스택이 하나 필요하다.
알고리듬은 다음과 같다.
- idx 값은 tail에서 head로 옮겨갈 tail의 원소의 인덱스 값이다. 초기값은 0이다.
- idx값에 해당하는 tail의 원소를 빼내어 head로 푸시한다.
- 2를 반복하여 tails가 비게되면? head에 들어있는 인덱스 값의 순서대로 원래 리스트에서 값을 추출하여 결과를 리턴한다. 맨 첫번째 시행에서는 리스트의 값 그대로가 출력된다.
- 이제 head에서 pop 하여 tails로 푸시한다. (이 때 tails는 매번 정렬한다.)
- idx값은 스택에서 팝 한 값에서 1을 더한 값이다.
- tail[1] 이 없으므로 head에서 하나 더 pop 하여 tail에 붙인다. (이
- tail[1]을 head로 푸시한다. 이 때 idx 값도 다시 스택에 푸시하고 idx값은 0이 된다.
- 2로 간다.
뭔가 많이 이상해보이지만, 이 과정을 반복하여 tails 가 빌 때 마다 head에 모여있는 인덱스의 순서대로 원소를 꺼내어 출력하면 사전식 순열이 된다.
인덱스스택, 인덱스, head, tail을 다음과 같이 추적해보자. 리스트 (‘1’, ‘2’, ‘3’, ‘4’)의 사전식 순열을 만들어서 출력하는 과정이다.
stack idx heads tails
--------------------------------------------------------
[] : 0 : [] : [0, 1, 2, 3] # tails[0]을 head로 이동
[0] : 0 : [0] : [1, 2, 3] # 계속해서 이동
[0, 0] : 0 : [0, 1] : [2, 3]
[0, 0, 0] : 0 : [0, 1, 2] : [3]
[0, 0, 0, 0] : 0 : [0, 1, 2, 3] : [] # tail이 비었다. 출력
--------------------------------------------------------
('1', '2', '3', '4')
--------------------------------------------------------
[0, 0, 0] : 1 : [0, 1, 2] : [3] # head의 맨 뒤 원소를 복구
# 인덱스는 스택에서 팝한 다음 1을 더한다. 이 때 tail[1] 없어서
[0, 0] : 1 : [0, 1] : [2, 3]
# 한 번 더 복구 tail[1] -> 3 이므로 이제는 다시 계속 진행한다. tails[1]을 head로 이동, idx 값은 스택에서 빼낸 값이 1을 더한 값이 된다. (이전에 뺀 값은 무시됨)
# idx를 푸시하고 다시 0으로 만든다. 다시 tail[idx]를 head로 푸시.
[0, 0, 1] : 0 : [0, 1, 3] : [2]
# head로 이동 반복
[0, 0, 1, 0] : 0 : [0, 1, 3, 2] : []
# tail이 비었으니 출력한다.
--------------------------------------------------------
('1', '2', '4', '3')
--------------------------------------------------------
# head에서 pop 하여 tail에 푸시. 그리고 idx 값을 꺼내와서 1더한다.
# tail[idx]에 해당하는 원소가 없으니 계속 위의 과정 반복
[0, 0, 1] : 1 : [0, 1, 3] : [2]
[0, 0] : 2 : [0, 1] : [2, 3]
[0] : 1 : [0] : [1, 2, 3]
# 꺼내오면서 tails는 정렬해줘야 한다. 이번에는 tail[1]이 존재하니 다시 정방향!
[0, 1] : 0 : [0, 2] : [1, 3]
[0, 1, 0] : 0 : [0, 2, 1] : [3]
[0, 1, 0, 0] : 0 : [0, 2, 1, 3] : []
--------------------------------------------------------
('1', '3', '2', '4')
--------------------------------------------------------
# 대략 알고리듬대로 진행하는 것이 눈에 익을 것이니 설명은 없어도 되겠지?
[0, 1, 0] : 1 : [0, 2, 1] : [3]
[0, 1] : 1 : [0, 2] : [1, 3]
[0, 1, 1] : 0 : [0, 2, 3] : [1]
[0, 1, 1, 0] : 0 : [0, 2, 3, 1] : []
--------------------------------------------------------
('1', '3', '4', '2')
--------------------------------------------------------
[0, 1, 1] : 1 : [0, 2, 3] : [1]
[0, 1] : 2 : [0, 2] : [1, 3]
[0] : 2 : [0] : [1, 2, 3]
[0, 2] : 0 : [0, 3] : [1, 2]
[0, 2, 0] : 0 : [0, 3, 1] : [2]
[0, 2, 0, 0] : 0 : [0, 3, 1, 2] : []
--------------------------------------------------------
('1', '4', '2', '3')
--------------------------------------------------------
[0, 2, 0] : 1 : [0, 3, 1] : [2]
[0, 2] : 1 : [0, 3] : [1, 2]
[0, 2, 1] : 0 : [0, 3, 2] : [1]
[0, 2, 1, 0] : 0 : [0, 3, 2, 1] : []
--------------------------------------------------------
('1', '4', '3', '2')
--------------------------------------------------------
[0, 2, 1] : 1 : [0, 3, 2] : [1]
[0, 2] : 2 : [0, 3] : [1, 2]
[0] : 3 : [0] : [1, 2, 3]
[] : 1 : [] : [0, 1, 2, 3]
[1] : 0 : [1] : [0, 2, 3]
[1, 0] : 0 : [1, 0] : [2, 3]
[1, 0, 0] : 0 : [1, 0, 2] : [3]
[1, 0, 0, 0] : 0 : [1, 0, 2, 3] : []
--------------------------------------------------------
('2', '1', '3', '4')
--------------------------------------------------------
[1, 0, 0] : 1 : [1, 0, 2] : [3]
[1, 0] : 1 : [1, 0] : [2, 3]
[1, 0, 1] : 0 : [1, 0, 3] : [2]
[1, 0, 1, 0] : 0 : [1, 0, 3, 2] : []
--------------------------------------------------------
('2', '1', '4', '3')
--------------------------------------------------------
[1, 0, 1] : 1 : [1, 0, 3] : [2]
[1, 0] : 2 : [1, 0] : [2, 3]
[1] : 1 : [1] : [0, 2, 3]
[1, 1] : 0 : [1, 2] : [0, 3]
[1, 1, 0] : 0 : [1, 2, 0] : [3]
[1, 1, 0, 0] : 0 : [1, 2, 0, 3] : []
--------------------------------------------------------
('2', '3', '1', '4')
--------------------------------------------------------
[1, 1, 0] : 1 : [1, 2, 0] : [3]
[1, 1] : 1 : [1, 2] : [0, 3]
[1, 1, 1] : 0 : [1, 2, 3] : [0]
[1, 1, 1, 0] : 0 : [1, 2, 3, 0] : []
--------------------------------------------------------
('2', '3', '4', '1')
--------------------------------------------------------
[1, 1, 1] : 1 : [1, 2, 3] : [0]
[1, 1] : 2 : [1, 2] : [0, 3]
[1] : 2 : [1] : [0, 2, 3]
[1, 2] : 0 : [1, 3] : [0, 2]
[1, 2, 0] : 0 : [1, 3, 0] : [2]
[1, 2, 0, 0] : 0 : [1, 3, 0, 2] : []
--------------------------------------------------------
('2', '4', '1', '3')
--------------------------------------------------------
[1, 2, 0] : 1 : [1, 3, 0] : [2]
[1, 2] : 1 : [1, 3] : [0, 2]
[1, 2, 1] : 0 : [1, 3, 2] : [0]
[1, 2, 1, 0] : 0 : [1, 3, 2, 0] : []
--------------------------------------------------------
('2', '4', '3', '1')
--------------------------------------------------------
[1, 2, 1] : 1 : [1, 3, 2] : [0]
[1, 2] : 2 : [1, 3] : [0, 2]
[1] : 3 : [1] : [0, 2, 3]
[] : 2 : [] : [0, 1, 2, 3]
[2] : 0 : [2] : [0, 1, 3]
[2, 0] : 0 : [2, 0] : [1, 3]
[2, 0, 0] : 0 : [2, 0, 1] : [3]
[2, 0, 0, 0] : 0 : [2, 0, 1, 3] : []
--------------------------------------------------------
('3', '1', '2', '4')
--------------------------------------------------------
[2, 0, 0] : 1 : [2, 0, 1] : [3]
[2, 0] : 1 : [2, 0] : [1, 3]
[2, 0, 1] : 0 : [2, 0, 3] : [1]
[2, 0, 1, 0] : 0 : [2, 0, 3, 1] : []
--------------------------------------------------------
('3', '1', '4', '2')
--------------------------------------------------------
[2, 0, 1] : 1 : [2, 0, 3] : [1]
[2, 0] : 2 : [2, 0] : [1, 3]
[2] : 1 : [2] : [0, 1, 3]
[2, 1] : 0 : [2, 1] : [0, 3]
[2, 1, 0] : 0 : [2, 1, 0] : [3]
[2, 1, 0, 0] : 0 : [2, 1, 0, 3] : []
--------------------------------------------------------
('3', '2', '1', '4')
--------------------------------------------------------
[2, 1, 0] : 1 : [2, 1, 0] : [3]
[2, 1] : 1 : [2, 1] : [0, 3]
[2, 1, 1] : 0 : [2, 1, 3] : [0]
[2, 1, 1, 0] : 0 : [2, 1, 3, 0] : []
--------------------------------------------------------
('3', '2', '4', '1')
--------------------------------------------------------
[2, 1, 1] : 1 : [2, 1, 3] : [0]
[2, 1] : 2 : [2, 1] : [0, 3]
[2] : 2 : [2] : [0, 1, 3]
[2, 2] : 0 : [2, 3] : [0, 1]
[2, 2, 0] : 0 : [2, 3, 0] : [1]
[2, 2, 0, 0] : 0 : [2, 3, 0, 1] : []
--------------------------------------------------------
('3', '4', '1', '2')
--------------------------------------------------------
[2, 2, 0] : 1 : [2, 3, 0] : [1]
[2, 2] : 1 : [2, 3] : [0, 1]
[2, 2, 1] : 0 : [2, 3, 1] : [0]
[2, 2, 1, 0] : 0 : [2, 3, 1, 0] : []
--------------------------------------------------------
('3', '4', '2', '1')
--------------------------------------------------------
[2, 2, 1] : 1 : [2, 3, 1] : [0]
[2, 2] : 2 : [2, 3] : [0, 1]
[2] : 3 : [2] : [0, 1, 3]
[] : 3 : [] : [0, 1, 2, 3]
[3] : 0 : [3] : [0, 1, 2]
[3, 0] : 0 : [3, 0] : [1, 2]
[3, 0, 0] : 0 : [3, 0, 1] : [2]
[3, 0, 0, 0] : 0 : [3, 0, 1, 2] : []
--------------------------------------------------------
('4', '1', '2', '3')
--------------------------------------------------------
[3, 0, 0] : 1 : [3, 0, 1] : [2]
[3, 0] : 1 : [3, 0] : [1, 2]
[3, 0, 1] : 0 : [3, 0, 2] : [1]
[3, 0, 1, 0] : 0 : [3, 0, 2, 1] : []
--------------------------------------------------------
('4', '1', '3', '2')
--------------------------------------------------------
[3, 0, 1] : 1 : [3, 0, 2] : [1]
[3, 0] : 2 : [3, 0] : [1, 2]
[3] : 1 : [3] : [0, 1, 2]
[3, 1] : 0 : [3, 1] : [0, 2]
[3, 1, 0] : 0 : [3, 1, 0] : [2]
[3, 1, 0, 0] : 0 : [3, 1, 0, 2] : []
--------------------------------------------------------
('4', '2', '1', '3')
--------------------------------------------------------
[3, 1, 0] : 1 : [3, 1, 0] : [2]
[3, 1] : 1 : [3, 1] : [0, 2]
[3, 1, 1] : 0 : [3, 1, 2] : [0]
[3, 1, 1, 0] : 0 : [3, 1, 2, 0] : []
--------------------------------------------------------
('4', '2', '3', '1')
--------------------------------------------------------
[3, 1, 1] : 1 : [3, 1, 2] : [0]
[3, 1] : 2 : [3, 1] : [0, 2]
[3] : 2 : [3] : [0, 1, 2]
[3, 2] : 0 : [3, 2] : [0, 1]
[3, 2, 0] : 0 : [3, 2, 0] : [1]
[3, 2, 0, 0] : 0 : [3, 2, 0, 1] : []
--------------------------------------------------------
('4', '3', '1', '2')
--------------------------------------------------------
[3, 2, 0] : 1 : [3, 2, 0] : [1]
[3, 2] : 1 : [3, 2] : [0, 1]
[3, 2, 1] : 0 : [3, 2, 1] : [0]
[3, 2, 1, 0] : 0 : [3, 2, 1, 0] : []
--------------------------------------------------------
('4', '3', '2', '1')
--------------------------------------------------------
이정도면 되는 것 같다. (실제로 이걸 짜기 위해서 종이에 1,2,3,4,5를 몇 장씩 이어서 써 내려갔다…)
아래는 이를 코드로 옮긴 것이다. 메모리를 적게 차지하면서도 비교적 나쁘지 않게 움직인다. (이걸로 오일러 프로젝트의 사전순 순열 100만번째 문제도 풀었다.)
def perm(iterable, r=None):
limit = len(iterable)
orders = range(limit)
heads = []
remains = orders
s_id = []
idx = 0
yield tuple([iterable[x] for x in range(limit)])
while not (s_id == [] and idx == limit):
if remains == []:
yield tuple([iterable[x] for x in heads])
if len(remains) > idx:
heads.append(remains.pop(idx))
s_id.append(idx)
idx = 0
elif len(remains) <= idx:
if s_id == []:
raise StopIteration
remains.append(heads.pop())
remains.sort()
idx = s_id.pop() + 1
그리고 아래는 스택 오버플로우에서 줏은 코드. 의외로 재귀함수내에서 yield를 썼는데 잘된다?
def permute(xs, low=0):
if low + 1 >= len(xs):
yield xs
else:
for p in permute(xs, low + 1):
yield p
for i in range(low + 1, len(xs)):
xs[low], xs[i] = xs[i], xs[low]
for p in permute(xs, low + 1):
yield p
xs[low], xs[i] = xs[i], xs[low]
for p in permute([1, 2, 3, 4]):
print p
사전식 순열을 찾는 보다 우아하면서도 고전적이고 더 단순한 알고리즘은 이미 오래전에 개발되어 있는데, 그냥 이런 식으로도 찾아보고 싶었다.
- 100개짜리 원소를 가진 집합의 순열의 개수는 100!로, `93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000’가지가 된다. ↩