Python에서 리스트의 모든 순열을 생성하는 알고리즘

2024-07-27

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

Python에서 리스트의 모든 순열을 생성하는 데에는 여러 가지 방법이 있습니다. 가장 일반적인 두 가지 방법은 다음과 같습니다.

재귀 알고리즘

재귀 알고리즘은 함수가 자기 자신을 호출하는 알고리즘입니다. 순열을 생성하는 데 사용할 수 있는 재귀 함수는 다음과 같습니다.

def permutations(arr, chosen=[]):
  if not arr:
    yield chosen
  else:
    for i in range(len(arr)):
      new_chosen = chosen + [arr[i]]
      new_arr = arr[:i] + arr[i+1:]
      yield from permutations(new_arr, new_chosen)

이 함수는 arr이라는 리스트와 chosen이라는 빈 리스트를 입력으로 받습니다. arr은 순열을 생성할 요소들을 포함하는 리스트이고, chosen은 현재까지 선택된 요소들을 포함하는 리스트입니다.

함수는 먼저 arr이 비어 있는지 확인합니다. 비어 있으면 chosen 리스트를 반환합니다. 즉, 현재까지 선택된 모든 요소들을 순열로 반환합니다.

arr이 비어 있지 않으면 for 루프를 통해 arr의 각 요소를 차례대로 선택합니다. 각 요소를 선택하면 chosen 리스트에 추가하고, arr 리스트에서 해당 요소를 제거합니다. 그런 다음 재귀적으로 permutations 함수를 호출하여 나머지 요소들의 순열을 생성합니다.

다음은 permutations 함수를 사용하여 1, 2, 3의 모든 순열을 생성하는 예입니다.

for permutation in permutations([1, 2, 3]):
  print(permutation)

이 코드는 다음과 같은 출력을 생성합니다.

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

itertools.permutations 모듈 사용

Python에는 itertools라는 모듈이 포함되어 있으며, 이 모듈에는 permutations 함수가 포함되어 있습니다. 이 함수는 주어진 리스트의 모든 순열을 이터레이터로 반환합니다.

import itertools

for permutation in itertools.permutations([1, 2, 3]):
  print(permutation)

이 코드는 위의 예와 동일한 출력을 생성합니다.

시간 복잡도

두 알고리즘 모두 시간 복잡도는 O(n!)입니다. 여기서 n은 리스트의 길이입니다.

선택

두 알고리즘 모두 리스트의 모든 순열을 생성하는 데 효과적입니다. 어떤 알고리즘을 사용할지는 개인의 선호에 따라 다릅니다. 재귀 알고리즘은 작동 방식을 이해하기 쉽지만, itertools.permutations 함수는 더 간결하고 명확합니다.

추가 정보

Python에서 리스트의 모든 순열을 생성하는 예제 코드

재귀 알고리즘

def permutations(arr, chosen=[]):
  if not arr:
    yield chosen
  else:
    for i in range(len(arr)):
      new_chosen = chosen + [arr[i]]
      new_arr = arr[:i] + arr[i+1:]
      yield from permutations(new_arr, new_chosen)

# 예제
for permutation in permutations([1, 2, 3]):
  print(permutation)

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

itertools.permutations 모듈 사용

import itertools

# 예제
for permutation in itertools.permutations([1, 2, 3]):
  print(permutation)

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

위의 코드에서 permutations 함수는 arr 리스트를 입력으로 받아 chosen 리스트를 반환합니다. chosen 리스트는 현재까지 선택된 요소들을 포함하는 리스트입니다. 함수는 먼저 arr이 비어 있는지 확인합니다. 비어 있으면 chosen 리스트를 반환합니다. 즉, 현재까지 선택된 모든 요소들을 순열로 반환합니다.

itertools.permutations 함수는 주어진 리스트의 모든 순열을 이터레이터로 반환합니다.

Python에서 리스트의 모든 순열을 생성하는 대체 방법

heappop 함수 사용

heappop 함수는 힙 자료구조에서 최소(또는 최대) 요소를 제거하는 데 사용되는 함수입니다. 순열을 생성하는 데 다음과 같이 사용할 수 있습니다.

import heapq

def permutations(arr):
  heapq.heapify(arr)
  while True:
    yield arr[:]
    if not next(is_heap_permutation(arr)):
      break
    heapq.heappush(arr, arr[0])
    arr[0], arr[-1] = arr[-1], arr[0]
    heapq.heapify(arr)

def is_heap_permutation(arr):
  for i in range(len(arr) // 2):
    if arr[2 * i + 1] < arr[i]:
      return False
  return True

# 예제
for permutation in permutations([1, 2, 3]):
  print(permutation)

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

라이브러리 사용

순열을 생성하는 데 도움이 되는 여러 라이브러리가 있습니다. 예를 들어, mathtools 라이브러리에는 permutations 함수가 포함되어 있으며, itertools 라이브러리에는 combinations 함수가 포함되어 있습니다.

import mathtools

# 예제
for permutation in mathtools.permutations([1, 2, 3]):
  print(permutation)

직접 구현

순열을 생성하는 알고리즘을 직접 구현할 수도 있습니다. 간단한 방법 중 하나는 다음과 같습니다.

def permutations(arr):
  if len(arr) == 0:
    yield []
  else:
    for i in range(len(arr)):
      new_arr = arr[:i] + arr[i+1:]
      for permutation in permutations(new_arr):
        yield [arr[i]] + permutation

# 예제
for permutation in permutations([1, 2, 3]):
  print(permutation)