Python에서 리스트의 모든 순열을 생성하는 알고리즘
[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)
선택
python algorithm permutation