문자열의 모든 순열(permutation)을 재귀 함수를 사용하지 않고 사전순(lexicographic order)으로 출력해야 하는 경우가 있습니다. 이럴 때는 문자열을 매개변수로 받는 하나의 메서드를 정의하고, 간단한 'for' 루프로 문자열의 요소를 반복 처리하며 'while' 조건문으로 특정 제약 조건을 검사하는 방식으로 문제를 해결할 수 있습니다.
핵심 아이디어는 흔히 '다음 순열(next permutation)' 알고리즘이라고 불리는 기법입니다. 현재 순열에서 사전순으로 바로 다음에 오는 순열을 찾아내는 과정을 문자열 길이의 팩토리얼(n!)만큼 반복하면, 재귀 호출 없이도 모든 순열을 순서대로 얻을 수 있습니다.
아래는 실제 구현 예시입니다.
예제
from math import factorial
def lex_permutation(my_string):
for i in range(factorial(len(my_string))):
print(''.join(my_string))
i = len(my_string) - 1
while i > 0 and my_string[i-1] > my_string[i]:
i -= 1
my_string[i:] = reversed(my_string[i:])
if i > 0:
q = i
while my_string[i-1] > my_string[q]:
q += 1
temp_variable = my_string[i-1]
my_string[i-1]= my_string[q]
my_string[q]= temp_variable
my_string = 'bhd'
print("The string is ")
print(my_string)
my_string = list(my_string)
print("The string is being sorted")
my_string.sort()
lex_permutation(my_string)
출력 결과
The string is
bhd
The string is being sorted
bdh
bhd
dbh
dhb
hbd
hdb
코드 설명
먼저 필요한 패키지를 가져옵니다. 여기서는 math 모듈의 factorial 함수를 사용합니다.
'lex_permutation'이라는 이름의 메서드를 정의하며, 이 메서드는 문자열을 매개변수로 받습니다.
factorial 메서드를 활용해 문자열 길이의 팩토리얼 값만큼 반복문을 수행합니다. 길이가 n인 문자열의 순열 개수는 n!이기 때문입니다.
while 루프를 통해 뒤쪽부터 내림차순으로 정렬된 구간을 찾아내고, 해당 구간을 뒤집어(reversed) 오름차순으로 만듭니다.
이후 적절한 위치의 두 문자를 서로 교환(swap)하여 다음 순열을 생성합니다.
메서드 외부에서 문자열 'bhd'를 정의하고 콘솔에 출력합니다.
문자열을 리스트로 변환한 뒤 오름차순으로 정렬합니다. 사전순 출력을 위해서는 반드시 가장 작은 순열부터 시작해야 하기 때문에 이 과정이 필수적입니다.
정렬된 문자열을 인자로 전달하며 메서드를 호출합니다.
모든 순열이 사전순으로 콘솔에 순서대로 출력됩니다.
참고 사항
이 알고리즘의 전체 시간 복잡도는 O(n × n!)이며, 재귀를 사용하지 않으므로 깊은 재귀 호출로 인한 스택 오버플로우 걱정 없이 안정적으로 동작한다는 장점이 있습니다. 다만 순열의 개수는 문자열 길이에 따라 기하급수적으로 증가하므로, 길이가 긴 문자열에는 적합하지 않다는 점을 유의해야 합니다.