파이썬 itertools의 순열 Permutations 구현

개요

파이썬의 itertools 라이브러리에는 데이터를 셀 수 있는 좋은 기능들이 많이 들어있다.

여기에 zip_longest나 조합인 combinations도 있다.

 

순열?

말 그대로 수학에 등장하는 nPr 이다.

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열이라고 한다.

중복 없이가 키 포인트라고 생각한다.

중복 순열, 중복 조합은 따로 존재하니 말이다.

 

공식적인 수학식은 아래와 같다.

파이썬에서의 순열

이제 파이썬에서 순열이 어떻게 작동하는지 보자.

from itertools import permutations

arr = [1,2,3,4,5]
per_arr = list(permutations(arr, 2))

print(per_arr)

#
[(1, 2), (1, 3), (1, 4), (1, 5), 
(2, 1), (2, 3), (2, 4), (2, 5), 
(3, 1), (3, 2), (3, 4), (3, 5), 
(4, 1), (4, 2), (4, 3), (4, 5), 
(5, 1), (5, 2), (5, 3), (5, 4)]
#

위처럼 나타나며, 출력 형식은 순열의 묶음마다 튜플로 감싸져 있고 그 밖을 리스트가 감싸고 있다.

자기 자신을 제외한 나머지 요소들과 순열 묶음을 이루고 있는 모습이다.

이걸 어떻게 구현할 수 있을까?

 

순열을 구현해보자

def my_permutations(iterable, number):
    visited = [False for _ in range(len(iterable))]		# 방문 체크를 위한 배열
    arr = [None for _ in range(number)]				# 요소를 담을 배열
    result = []							# 순열끼리 묶인 데이터를 담을 배열
    
    def permutation(depth):					# 재귀를 통해 순열을 만들어줄 함수
        if depth == number:					# v는 기준이 되는 인덱스인데 이 값이 담아야할 요소의 개수인 number와 같아졌다는 건
            result.append(tuple(arr))				# 한 튜플 안에 담을 개수를 모두 담았다는 의미, 그래서 append를 해준다.
        else:
            for i in range(len(iterable)):
                if not visited[i]:				# 이 체크 때문에 (1,1)처럼 중복인 게 들어갈 수는 없다.
                    visited[i] = True
                    arr[depth] = iterable[i]			# 순열에 들어갈 값 넣어주기
                    permutation(depth + 1)			# 다음 탐색을 진행할 때는 다음 숫자를(0번 인덱스에서 1번 인덱스...)기준으로 탐색할 수 있도록
                    visited[i] = False				# 여기서 False를 해줘야 다른 숫자가 기준일 때 순열을 만들 수 있다.
    permutation(0)						# 0번 인덱스에서 시작하는 건 고정이니까
    
    return result

arr = [1,2,3,4,5]
per_arr = list(my_permutations(arr, 2))

print(per_arr)

헤맸던 부분은 튜플 묶음 안에 number의 수만큼 순열을 담았을 때 어떻게 밖으로 반환을 해줘야할지의 부분이었다.

분명 1차적으로 감싸고 있는 건 튜플인데 그리고 제네레이터 형식인 것 같은데 어떻게 밖으로 빼는 거지 싶었다.

그래서 yield를 하니 자꾸 Nonetype에러가 뜨는 것이다.

 

해결책으로 어떻게든 일단 반환은 시켜보자라는 일념으로 배열을 하나 만들고 반환을 했더니 알고보니 저렇게 하는 게 맞았던 것이다.

뒷걸음질 치다가 성공했다.