재귀(recursion)를 활용해 문자열의 모든 순열(permutation)을 사전순(lexicographic order)으로 출력해야 하는 경우, for 루프로 요소 시퀀스를 반복하고 join() 메서드로 각 요소를 하나의 문자열로 연결하는 메서드를 정의하면 됩니다. 아래 예제를 통해 구현 방법을 살펴보겠습니다.
예제 코드
from math import factorial
def lexicographic_permutation_order(s):
my_sequence = list(s)
for _ in range(factorial(len(my_sequence))):
print(''.join(my_sequence))
next = next_in_permutation(my_sequence)
if next is None:
my_sequence.reverse()
else:
my_sequence = next
def next_in_permutation(my_sequence):
if len(my_sequence) == 0:
return None
next = next_in_permutation(my_sequence[1:])
if next is None:
my_sequence[1:] = reversed(my_sequence[1:])
q = 1
while q < len(my_sequence) and my_sequence[0] > my_sequence[q]:
q += 1
if q == len(my_sequence):
return None
my_sequence[0], my_sequence[q] = my_sequence[q], my_sequence[0]
return my_sequence
else:
return [my_sequence[0]] + next
my_input = input('문자열을 입력하세요 : ')
print("입력된 문자열 :")
print(my_input)
print("메서드를 호출합니다...")
lexicographic_permutation_order(my_input)
실행 결과
문자열을 입력하세요 : hey 입력된 문자열 : hey 메서드를 호출합니다... hey hye yeh yhe hey hye
코드 설명
math.factorial을 임포트하여 길이가 n인 문자열의 순열 총 개수(n!)를 계산하는 데 사용합니다.
lexicographic_permutation_order 메서드는 입력 문자열을 리스트로 변환한 뒤, n!번 반복하면서 현재 순열을 출력하고 다음 순열을 구합니다.
next_in_permutation 메서드는 재귀 호출을 통해 현재 배열에서 사전순으로 바로 다음에 오는 순열을 찾아내는 역할을 합니다.
사용자에게 문자열을 입력받아 콘솔에 표시합니다.
입력받은 문자열을 매개변수로 전달하며 메서드를 호출합니다.
생성된 모든 순열이 콘솔에 순차적으로 출력됩니다.
다음 순열을 찾는 원리
next_in_permutation 함수는 문자열의 뒷부분(접미사)을 재귀적으로 처리합니다. 더 이상 새로운 순열을 만들 수 없어 None이 반환되면, 나머지 부분을 역순으로 뒤집고 첫 번째 문자를 적절한 위치의 문자와 맞바꿔 다음 순열을 완성합니다. 만약 마지막 순열(역순 정렬 상태)에 도달하면 None을 반환하며, 이때 호출부에서는 리스트 전체를 뒤집어 다시 처음 상태로 되돌립니다. 이 때문에 위 실행 결과에서처럼 순열이 다시 처음부터 반복되는 모습을 확인할 수 있습니다.
이 알고리즘은 별도의 정렬 과정 없이도 순열을 사전순으로 생성할 수 있다는 장점이 있으며, itertools.permutations 같은 내장 도구의 동작 원리를 직접 구현해보고 싶을 때 유용한 학습 예제가 됩니다.