문자열이 주어졌을 때, 해당 문자열로 만들 수 있는 모든 순열(permutation)을 화면에 출력하는 것이 이번 글의 목표입니다. 파이썬에서는 itertools 모듈의 내장 함수인 permutations(iterable)을 사용하면 복잡한 재귀 알고리즘을 직접 작성하지 않고도 손쉽게 해결할 수 있습니다.
문제 예시
예를 들어 문자열 'XYZ'가 주어지면, 세 글자의 위치를 모두 바꿔가며 만들 수 있는 경우의 수는 다음과 같습니다.
입력: string = 'XYZ'
출력: XYZ
XZY
YXZ
YZX
ZXY
ZYX
길이가 n인 문자열의 순열 개수는 n!개이므로, 'XYZ'는 3! = 6가지 조합이 나오게 됩니다.
알고리즘
전체적인 풀이 과정은 아래와 같습니다.
1단계: 문자열을 입력받습니다. 2단계: permutations() 함수를 호출하여 문자열의 모든 순열을 생성합니다. 3단계: 생성된 순열을 하나씩 꺼내어 출력합니다.
예제 코드
from itertools import permutations
def allPermutations(str1):
# 문자열의 모든 순열을 가져옵니다
per = permutations(str1)
# 모든 순열을 출력합니다
print("Permutation Of this String ::>")
for i in list(per):
print(''.join(i))
# 메인 프로그램
if __name__ == "__main__":
str1 = input("Enter the string ::>")
allPermutations(str1)
코드 설명
permutations(str1): 문자열을 iterable로 전달하면 각 요소(문자)의 모든 순열을 튜플 형태로 반환하는 iterator를 생성합니다.''.join(i): 반환된 튜플 예를 들어 ('a', 'b', 'c')를 다시 하나의 문자열 'abc'로 합쳐줍니다.list(per): iterator를 리스트로 변환하여 반복문에서 순서대로 처리할 수 있도록 합니다.
실행 결과
Enter the string ::> abc Permutation Of this String ::> abc acb bac bca cab cba
위 실행 결과에서 확인할 수 있듯이, 'abc'로 만들 수 있는 총 6가지(3!) 순열이 사전순으로 정렬되어 출력됩니다. 이처럼 itertools.permutations()를 활용하면 단 몇 줄의 코드로 문자열 순열 문제를 깔끔하게 해결할 수 있습니다.