파이썬에서 주어진 문자열의 가능한 모든 순열(permutation)을 구하는 가장 간단한 방법은 표준 라이브러리인 itertools 모듈을 활용하는 것입니다. 이 모듈에는 permutations(iterable[, r])이라는 유용한 메서드가 포함되어 있으며, 이 함수는 iterable의 요소들로 만들 수 있는 길이 r의 순열을 튜플(tuple) 형태로 하나씩 차례대로 반환합니다.
itertools.permutations로 순열 구하기
순열 결과를 문자열 형태로 얻으려면 함수 호출 결과를 반복(iterate)하면서 각 튜플을 join()으로 이어 붙이면 됩니다. 아래 예제를 살펴보세요.
from itertools import permutations
result = [''.join(p) for p in permutations('dune')]
print(result)['dune', 'duen', 'dnue', 'dneu', 'deun', 'denu', 'udne', 'uden', 'unde', 'uned', 'uedn', 'uend', 'ndue', 'ndeu', 'nude', 'nued', 'nedu', 'neud', 'edun', 'ednu', 'eudn', 'eund', 'endu', 'enud']
'dune'처럼 서로 다른 4개의 문자로 이루어진 문자열의 순열 개수는 4! = 24개입니다. 일반적으로 길이가 n인 문자열의 순열은 총 n!개 생성되므로, 문자열이 길어질수록 결과의 개수가 기하급수적으로 늘어난다는 점을 유의해야 합니다.
재귀 함수로 직접 구현하기
내장 모듈을 사용하지 않고 직접 구현하고 싶다면 다음과 같은 재귀(recursive) 방식을 사용할 수 있습니다. 이 알고리즘은 각 단계에서 한 문자를 고정한 뒤, 나머지 문자들을 재귀적으로 교환(swap)하면서 모든 경우의 수를 탐색합니다.
def permutations(string, step=0):
# 문자열의 끝에 도달하면 완성된 순열을 출력
if step == len(string):
print(''.join(string))
return
for i in range(step, len(string)):
# 문자열을 리스트 형태로 복사
string_copy = [c for c in string]
# 현재 위치(step)의 문자와 i번째 문자를 교환
string_copy[step], string_copy[i] = string_copy[i], string_copy[step]
# 아직 교환되지 않은 부분에 대해 재귀 호출
permutations(string_copy, step + 1)
permutations('one')실행 결과는 다음과 같습니다.
one oen noe neo eno eon
원본 예제 코드에는 들여쓰기 오류와 함수 호출을 print()로 감싸면서 None이 함께 출력되는 문제가 있었지만, 위 코드에서는 이러한 부분을 정리하여 깔끔하게 동작하도록 수정했습니다.
알아두면 좋은 팁
- 중복 제거: 문자열에 같은 문자가 여러 번 포함된 경우(예: 'aab') 동일한 순열이 중복해서 출력될 수 있습니다. 이럴 때는 결과를
set()에 담거나itertools.permutations의 결과에set()을 적용하면 중복을 손쉽게 제거할 수 있습니다. - 결과를 값으로 반환하기: 화면에 출력하는 대신 리스트로 받아 활용하고 싶다면, 재귀 함수 내부에서
print()대신 결과를 리스트에append()한 후 반환하도록 수정하면 됩니다. - 성능 주의: 순열의 개수는 n!로 증가하기 때문에, 문자열 길이가 10을 넘어가면 계산량이 매우 커집니다. 실무에서는 필요한 길이(r)만 지정하여
permutations(string, r)형태로 사용하는 것이 효율적입니다.