주어진 문자열로 만들 수 있는 모든 문자 반복 조합(중복 순열)을 구해야 하는 경우, 인덱스 값을 활용하는 재귀 함수를 정의하여 각 조합을 사전순으로 출력할 수 있습니다. 이 방식은 각 자리에 들어갈 문자를 하나씩 채워 나가는 깊이 우선 탐색과 유사한 원리로 동작합니다.
예제 코드
아래는 이를 구현한 예제입니다.
def to_string(my_list):
return ''.join(my_list)
def lex_recurrence(my_string, my_data, last_val, index_val):
length = len(my_string)
for i in range(length):
my_data[index_val] = my_string[i]
if index_val == last_val:
print(to_string(my_data))
else:
lex_recurrence(my_string, my_data, last_val, index_val+1)
def all_lex(my_string):
length = len(my_string)
my_data = [""] * (length+1)
my_string = sorted(my_string)
lex_recurrence(my_string, my_data, length-1, 0)
my_string = "MQ"
print("The string is :")
print(my_string)
print("All permutations with repetition of " + my_string + " are...")
all_lex(my_string)
실행 결과
The string is : MQ All permutations with repetition of MQ are... MM MQ QM QQ
코드 설명
'to_string'이라는 함수를 정의합니다. 이 함수는 리스트를 매개변수로 받아 모든 요소를 join으로 연결한 하나의 문자열로 반환합니다.
'lex_recurrence'라는 재귀 함수를 정의합니다. 이 함수는 대상 문자열, 결과를 저장할 리스트, 마지막 인덱스 값, 현재 인덱스 값을 매개변수로 받습니다.
함수는 문자열의 길이만큼 반복하면서 현재 인덱스 위치에 문자를 하나씩 채워 넣습니다.
현재 인덱스 값이 마지막 인덱스 값과 같으면, 완성된 조합을 하나의 결과로 출력합니다.
그렇지 않다면, 인덱스 값을 1 증가시켜 자기 자신을 다시 호출하는 재귀 과정을 반복합니다.
'all_lex' 함수는 sorted 메서드를 사용해 입력 문자열을 사전순으로 정렬한 뒤, 앞서 정의한 재귀 함수를 호출해 전체 조합 생성을 시작합니다.
함수 외부에서 문자열을 정의하고 콘솔에 출력한 뒤, all_lex 함수를 호출합니다.
최종적으로 가능한 모든 중복 순열이 콘솔에 표시됩니다.
길이가 n인 문자열의 중복 순열 개수는 n의 n제곱(nn)이므로, 입력 문자열이 길어질수록 생성되는 조합의 수가 기하급수적으로 증가한다는 점에 유의해야 합니다. 따라서 이 기법은 비교적 짧은 문자열을 다룰 때 가장 적합합니다.