Python에서 목록의 모든 순열을 생성하는 방법

Python 표준 라이브러리로 목록의 순열을 생성하거나, 과정을 직접 제어해야 한다면 재귀 또는 반복 알고리즘을 사용할 수 있습니다. 순열은 선택한 원소를 순서 있게 배열한 것입니다. 조합과 달리 순서가 중요합니다. 결과 개수는 팩토리얼에 따라 늘어나므로 모든 배열을 생성하는 작업은 입력이 그리 크지 않을 때만 실용적입니다.

itertools 라이브러리 사용하기

대부분의 경우 itertools.permutations를 사용하면 됩니다. 이 함수는 튜플 이터레이터를 반환하므로 결과를 한꺼번에 목록으로 만들지 않고 하나씩 처리할 수 있습니다. 기본적으로 r은 입력 길이와 같아서 각 결과에 모든 원소가 포함됩니다. 아래 예제에서 r=2는 순서가 있는 두 원소짜리 묶음을 선택하며, 반복문은 길이 1부터 3까지 각각 생성합니다.

목록 [1, 2, 3]을 사용하면 프로그램은 다음을 출력합니다.

from itertools import permutations

data = [1, 2, 3]
print("full:", list(permutations(data)))
print("length 2:", list(permutations(data, r=2)))
print("lengths 1 to 3:")
for r in range(1, len(data) + 1):
    print(r, list(permutations(data, r)))

full: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
length 2: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
lengths 1 to 3:
1 [(1,), (2,), (3,)]
2 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
3 [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

r 인수는 각 튜플에 들어갈 원소 수를 정합니다. 모든 비어 있지 않은 길이의 순열이 필요하면 위 예제처럼 r을 1부터 입력 길이까지 바꾸어 함수를 호출하면 됩니다. itertools.permutations는 값의 동일 여부가 아니라 원소의 위치를 기준으로 처리합니다. 따라서 입력에 같은 값이 여러 번 있으면 결과 튜플도 중복될 수 있습니다.

함수의 전체 서명과 동작은 공식 itertools 문서를 참조하세요.

순열을 구하는 재귀 함수

재귀 방식은 원소를 하나씩 선택한 다음, 그 원소를 나머지 원소들의 각 순열 앞에 붙입니다. 기저 사례는 빈 배열 하나를 담은 목록을 반환합니다. 덕분에 입력 길이가 0인 경우를 포함해 어떤 길이에서도 구성이 성립합니다. 이 구현은 튜플이 아니라 목록을 반환하며, 순열을 직접 구성하거나 그 과정을 학습하고 싶을 때 유용합니다.

def permute(data):
    if not data:
        return [[]]

    result = []
    for index, item in enumerate(data):
        remaining = data[:index] + data[index + 1:]
        for tail in permute(remaining):
            result.append([item] + tail)
    return result

print(permute([1, 2, 3]))

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

재귀 호출을 할 때마다 위치 하나를 제거하므로, 기저 사례에 도달할 때까지 입력이 작아집니다. 서로 다른 위치에 있는 값이 같으면 이 구현에서도 같은 목록이 여러 번 나올 수 있습니다. 전체 결과를 저장하고 재귀 호출도 많이 수행하므로 학습이나 작은 입력에 적합합니다. 직접 구성을 바꿀 필요가 없다면 표준 라이브러리의 이터레이터를 사용하세요.

순열을 생성하는 반복 방식

이미 모아 둔 부분 배열의 모든 위치에 새 원소를 삽입해 결과를 만들 수도 있습니다. 목록은 빈 배열 하나로 시작합니다. 새 원소를 처리할 때마다 기존 각 결과의 가능한 삽입 위치 수, 즉 지금까지 처리한 원소 수만큼 결과 개수가 곱해집니다. 재귀 호출은 피하지만 모든 결과를 계속 메모리에 저장합니다.

def iterative_permute(data):
    results = [[]]
    for item in data:
        next_results = []
        for ordering in results:
            for index in range(len(ordering) + 1):
                next_results.append(ordering[:index] + [item] + ordering[index:])
        results = next_results
    return results

print(iterative_permute([1, 2, 3]))

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

삽입 순서는 이 방식이 결과를 반환하는 순서만 결정하며, 생성되는 순열의 종류는 바꾸지 않습니다. 단계별 구성이 작업에 적합할 때 선택하되, 전체 결과를 유지하는 데 필요한 메모리를 고려하세요.

결론

간결한 지연 평가 이터레이터가 필요하면 itertools.permutations를 사용하고, 특정 길이만 필요하면 r을 지정하세요. 구성을 직접 바꾸거나 학습하려면 재귀 또는 반복 삽입 방식을 사용할 수 있습니다. 위치가 서로 다른 길이 n의 목록에는 길이 전체를 사용하는 순열이 n!개 있으므로, 처리 시간과 결과를 목록으로 저장하는 데 필요한 공간이 빠르게 늘어납니다. 입력이 크다면 이터레이터를 필요한 만큼 처리하거나, 문제에 필요한 길이와 선택만 생성하세요.

자주 묻는 질문

1. 순열이란 무엇인가요?
   원소를 순서 있게 선택한 것입니다. 예를 들어 [1, 2]와 [2, 1]은 순서가 다르므로 서로 다른 순열입니다.

2. itertools.permutations는 어떻게 동작하나요?
   입력 이터러블에서 길이가 r인 튜플을 생성합니다. r을 생략하면 입력 전체 길이를 사용합니다. 결과는 지연 생성되지만 이터레이터를 목록으로 변환하면 모든 결과가 메모리에 저장됩니다.

3. 입력에 중복 값이 있으면 어떻게 되나요?
   이 함수는 값이 같은지 여부가 아니라 각 위치를 기준으로 원소를 처리합니다. 따라서 입력 값이 중복되면 동일한 튜플이 여러 번 생성될 수 있습니다. 모든 결과를 만든 뒤 집합으로 변환하면 원소를 해시할 수 있는 경우 중복 튜플을 제거할 수 있지만, 중복 결과를 만드는 작업 자체를 줄이지는 못합니다. 중복 계산을 피하려면 각 단계에서 같은 값을 건너뛰는 알고리즘을 사용하세요.

4. 순열은 몇 개나 생성되나요?
   서로 다른 n개 위치의 원소를 모두 사용하는 순열은 n!개입니다. 그중 r개 위치만 선택하면 개수는 n! / (n - r)!입니다.

5. 입력을 얼마나 크게 해도 되나요?
   모든 컴퓨터와 작업에 적용되는 단일 크기 제한은 없습니다. 팩토리얼에 따른 결과 수 때문에 중간 크기의 입력도 처리 비용이 클 수 있고, 결과를 전부 저장하면 상당한 메모리가 필요합니다. 전체 길이의 결과를 한꺼번에 보관할 필요가 없다면 지연 이터레이터를 사용하거나 r을 줄이세요.