순열(Permutation)이란 여러 개의 객체를 서로 다른 순서로 배열할 수 있는 모든 경우의 수를 의미합니다. 하지만 주어진 객체 목록 안에 동일한 객체가 두 개 이상 포함되어 있다면, 서로 다른 순열끼리 결과가 같아지는 경우가 발생합니다. 이 글에서는 객체 목록에서 중복을 제거한 고유한 순열만 추출하여 원하는 개수만큼 출력하는 방법을 알아보겠습니다.
itertools.permutations와 set 활용하기
Python의 표준 라이브러리인 itertools 모듈에는 permutations라는 메서드가 있어 순열 생성을 손쉽게 처리할 수 있습니다.
다만 permutations는 입력에 중복된 문자가 있으면 동일한 결과를 여러 번 반환하므로, 고유한 순열만 얻으려면 추가 처리가 필요합니다. 여기서는 중복되지 않은 요소만 저장하는 set(집합) 자료구조를 활용합니다. 또한 결과를 일관성 있게 만들기 위해 sorted 메서드로 요소를 미리 정렬한 후 순열을 생성합니다.
아래 프로그램에서 K는 전체 가능한 고유 순열 중에서 화면에 표시하고 싶은 최대 개수입니다. while 루프를 돌면서 각 순열이 아직 집합에 없는 경우에만 최종 목록에 추가하고 출력함으로써, 정확히 k개의 고유한 순열만 얻을 수 있습니다.
예제 코드
from itertools import permutations
def permutation_value(str, k):
s = sorted(list(str))
p = permutations(s)
m = 0
set_1 = set()
str = ''
while m < k:
str = ''.join(p.__next__())
if str not in set_1:
set_1.add(str)
print(str)
m += 1
str = "xyxxz"
i = 12
permutation_value(str, i)
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
xxxyz
xxxzy
xxyxz
xxyzx
xxzxy
xxzyx
xyxxz
xyxzx
xyzxx
xzxxy
xzxyx
xzyxx
코드 동작 방식 정리
1. sorted(list(str))로 문자열의 문자들을 사전순으로 정렬합니다.
2. permutations(s)로 정렬된 문자들의 모든 순열을 생성하는 반복자를 만듭니다.
3. while 루프에서 p.__next__()로 순열을 하나씩 꺼내 문자열로 조인합니다.
4. 해당 문자열이 set_1에 없을 때만 집합에 추가하고 출력하며, 카운터 m을 1 증가시킵니다.
5. m이 k에 도달하면 루프가 종료되어, 정확히 k개의 고유한 순열만 출력됩니다.
이 방식은 중복 문자가 많은 문자열에서도 불필요한 중복 출력 없이 원하는 개수의 고유 순열을 효율적으로 확인할 수 있게 해줍니다.