파이썬으로 주어진 문자열의 모든 순열 출력하기

이 글에서는 아래에 제시된 문제에 대한 해결 방법을 자세히 알아보겠습니다.

문제 정의

하나의 문자열이 주어졌을 때, 그 문자열의 문자들을 재배치하여 만들 수 있는 모든 순열(permutation)을 출력하는 프로그램을 작성해야 합니다. 예를 들어 'TUT'라는 문자열이 주어지면 TUT, TTU, UTT 등 가능한 모든 조합을 화면에 표시해야 합니다.

그럼 이제 아래 구현 예시를 통해 해결 방법을 살펴보겠습니다.

구현 예시

# 문자 리스트를 문자열로 변환
def toString(List):
    return ''.join(List)

# 순열 생성 함수
def permute(a, l, r):
    if l == r:
        print(toString(a))
    else:
        for i in range(l, r + 1):
            a[l], a[i] = a[i], a[l]   # 현재 위치의 문자와 i번째 문자 교환
            permute(a, l + 1, r)      # 다음 위치에 대해 재귀 호출
            a[l], a[i] = a[i], a[l]   # 백트래킹(원래 상태로 복원)

# 메인 실행부
string = "TUT"
n = len(string)
a = list(string)
print("The possible permutations are:", end="\n")
permute(a, 0, n-1)

실행 결과

The possible permutations are:
TUT
TTU
UTT
UTT
TUT
TTU

동작 원리

위 코드에서 사용된 모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 변수의 참조 관계는 위 실행 흐름에서 확인할 수 있습니다.

permute 함수는 재귀 호출과 백트래킹(backtracking) 기법을 활용합니다. 먼저 현재 위치(l)의 문자를 나머지 위치의 문자와 하나씩 교환한 뒤, 다음 위치에 대해 같은 과정을 재귀적으로 반복합니다. 한 분기의 탐색이 끝나면 문자를 원래대로 되돌려 다른 조합을 탐색할 수 있도록 하는데, 이것이 바로 백트래킹입니다. 왼쪽 인덱스 l이 오른쪽 인덱스 r과 같아지면 더 이상 교환할 문자가 남아 있지 않다는 의미이므로, 완성된 순열 하나를 출력하게 됩니다.

참고로 입력 문자열에 중복 문자가 포함된 경우('TUT'처럼 T가 두 번 등장하는 경우) 동일한 결과가 여러 번 출력될 수 있습니다. 중복 없이 고유한 순열만 얻고 싶다면 결과를 set 자료형으로 필터링하거나, 표준 라이브러리의 itertools.permutations를 활용하는 방법도 좋은 대안입니다.

결론

이 글에서는 파이썬을 사용하여 주어진 문자열의 모든 순열을 출력하는 프로그램을 만드는 방법을 배웠습니다. 재귀 호출과 백트래킹의 기본 개념만 이해하면, 문자열뿐만 아니라 리스트 등 다른 자료형에도 같은 원리를 손쉽게 적용할 수 있습니다.