파이썬(Python)으로 집합의 모든 순열(Permutation) 생성하는 3가지 방법

수학에서 집합의 모든 원소를 특정 순서나 배열로 나열하는 것을 순열(permutation)이라고 합니다. 이미 정렬되어 있는 집합이라면 그 원소들을 다시 재배열(reordering)하는 것 역시 순열에 해당합니다.

파이썬에서는 다양한 기법으로 순열을 생성할 수 있으며, 이 글에서는 가장 많이 활용되는 세 가지 방법을 소개합니다.

방법 1: itertools 모듈 활용

파이썬은 순열과 조합을 위한 전용 모듈인 itertools를 표준 라이브러리로 제공합니다. 별도의 설치 없이 바로 사용할 수 있어 가장 간편한 방법입니다.

모듈 임포트

>>> import itertools

permutations 함수를 사용하면 리스트 안에서 N개 값의 순열을 구할 수 있으며, 이때 순서가 중요합니다. 예를 들어 [1, 2, 3, 4]에서 N=2개의 값을 선택하는 경우는 다음과 같습니다.

순열 (순서가 중요함):
>>> print(list(itertools.permutations([1,2,3,4],2)))
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

반면 순서가 중요하지 않은 조합(combination)이 필요하다면 combinations 함수를 사용하면 됩니다.

>>> print(list(itertools.combinations('1234', 2)))
[('1', '2'), ('1', '3'), ('1', '4'), ('2', '3'), ('2', '4'), ('3', '4')]

방법 2: 중간 리스트 없이 제너레이터로 구현

외부 모듈 없이 직접 구현하고 싶다면 아래와 같이 작성할 수 있습니다. 이 방식은 새로운 중간 리스트를 생성하지 않고 원본 리스트에서 요소의 위치를 교환(swap)하며 순열을 만들어내므로 메모리 효율이 좋습니다.

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]):
    print(p)

실행 결과

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

방법 3: 재귀(Recursion) 함수 활용

재귀 호출을 이용해 순열을 생성하는 방법도 있습니다. 접두사(prefix) 부분과 나머지(rest) 부분으로 나누어, 나머지에서 하나씩 원소를 꺼내 접두사에 붙이는 방식으로 동작합니다.

import copy

def perm(prefix, rest):
    for e in rest:
        new_rest = copy.copy(rest)
        new_prefix = copy.copy(prefix)
        new_prefix.append(e)
        new_rest.remove(e)
        if len(new_rest) == 0:
            print(new_prefix + new_rest)
            continue
        perm(new_prefix, new_rest)

perm([], [1, 2, 3])

실행 결과

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

정리

실무에서는 표준 라이브러리인 itertools.permutations를 사용하는 것이 가장 안전하고 성능도 우수합니다. 반면 알고리즘 학습이나 면접 준비 목적이라면 제너레이터 기반 구현과 재귀 구현을 직접 작성해 보며 순열의 동작 원리를 깊이 이해하는 것이 큰 도움이 됩니다.