순열 조합 생성하기

어떤 집합의 각 원소들을 사용해서 만들 수 있는 모든 순열이나 조합을 만들어야 하는 경우에는 표준 라이브러리의 itertools 모듈을 사용할 수 있습니다. itertools.permutations()와 itertools.combinations()를 사용하면 모든 순열과 조합을 생성해 볼 수 있습니다.

이번 시간에는 순열, 조합 생성기를 직접 구현하는 방법에 대해서 살펴보겠습니다. 의외로 무척 간단하게 구현할 수 있습니다.

순열 생성하기

A, B, C, D의 네 개의 원소에 대한 모든 순열을 만든다고 가정해보겠습니다. 먼저 첫번째 원소를 A라고 정해보겠습니다. 첫 번째 원소가 결정되었다면, 나머지 3개의 원소를 이용해서 만들 수 있는 모든 순열을 구한 다음, 각각의 결과의 맨 앞에 A를 붙이면 됩니다. 그런 다음 다시 첫번째 원소로 B를 정하고 같은 일을 반복합니다.

앞을 정하고 나머지 부분에 대해서 같은 일을 반복하는 이 과정은 재귀 알고리듬으로 구현하기에 딱 알맞습니다. 그러나 순열의 개수는 원소의 수의 팩토리얼에 해당하므로 한 번에 모든 순열을 생성하는 것은 메모리를 너무 많이 사용합니다. 따라서 제너레이터로 구현하는 것이 좋겠습니다.

제너레이터를 재귀적으로 사용할 때에는 yield from 구문을 사용하면 됩니다.

def permutations(xs, n=0):
  def _helper(head, tail, k):
    if k == 0:
      yiled head
      return
    for (i, x) in enumerated(tail):
      yield from _helper((*acc, x), (*tail[:i], *tail[i+1:]), k - 1)

  yield from _helper(tuple(), tuple(xs), n if n > 0 else len(xs))


A = [1, 2, 3, 4]
for xs in permutations(A, 3):
  print(xs)

사실 이 재귀 구조는 순열 생성 함수나 조합 생성 함수나 대동소이 합니다. 앞에서 결정된 원소들과 뒤에서 결정될 원소들을 어떻게 나눌 것인지만 결정하면서 원소가 하나 결정될 때마다 크기값 k를 1씩 줄여나가면서 0이 될 때까지 반복하기만 하면 됩니다.

조합 생성하기

조합의 경우에도 순열과 거의 같습니다. 단, 순열의 경우에는 (A, B, C)와 (B, A, C)가 다릅니다만 조합에서는 같은 것으로 봐야 합니다. 따라서 모든 조합의 경우를 만들고 원소를 순서대로 정렬한다면, 앞에서 이미 선택했던 원소는 더 이상 나오지 않으면 됩니다.

def combinations(xs, n=0):
  def _helper(head, tail, k):
    if k == 0:
      yield head
      return
    for (i, x) in enumerated(tail):
      yield from _helper((*acc, x), *tail[i+1:], k - 1)

  yield from _helper(tuple(), tuple(xs), n if n > 0 else len(xs))


A = [1, 2, 3, 4]
for xs in combinations(A, 3):
  print(xs)

어디가 달라졌는지 살짝 눈치채셨나요?

중복된 것들을 포함하는 순열의 생성

이번에는 [A, A, A, B, B, C] 중에서 4개를 골라 만들 수 있는 순열을 모두 구하는 제너레이터를 만들어보겠습니다. 이런 종류의 문제는 수학 시간에 잘 나오는데, 만들 수 있는 순열의 가짓수를 구하는 것은 쉽지만, 일일이 순열을 만드는 것은 여간 헷갈리는 일이 아닐 수 없습니다.

중복을 포함하는 경우의 순열은 카운터(Counter)를 사용하여, 중복된 요소는 그 개수까지만 사용할 수 있도록 조합하고 다른 원소들끼리는 순열을 이루도록 합니다. 말로하자니 크게 달라 보일 법도 한데, 제너레이터의 재귀 호출이라는 구조는 동일하고 코드 자체도 크게 다르지 않아 보입니다.

from collections import Counter

def perms_on_dups(xs, n):
  def helper(head, counter, k):
    if k == 0:
      yield head
      return
    for (x, c) in counter.items():
      if c == 0:
        continue
      yield from helper((*head, x), {**counter, x: c - 1}, k - 1)

  yield from helper(tuple(), Counter(xs), n if n > 0 else len(xs))