[Algorithm] Permutation Algorithm(순열 알고리즘) with Python

순열.. 순열이 뭘까!

 

순열은 보통 고등학교 수학 시간에 배운다.

 

수학에서, 순열(Permutation) 또는 치환은 서로 다른 n개의 원소에서 r(<=n)개를 뽑아 한 줄로 세우는 경우의 수이며, nPr이라고 나타낸다. 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역과 공역이 같은 일대일 대응이다. n개의 원소의 순서를 뒤섞는 순열의 개수는 n의 계승 n!와 같다. 즉, n 이하의 양의 정수들을 곱한 값이다.

 

위키백과에 나오는 순열에 대한 글귀다.

 

우리가 알아야 할 정보는 순열이란 서로 다른 n개의 원소에서 r(<=n)개를 뽑아 한 줄로 세우는 경우의 수이고, 이것을 nPr이라고 나타낸다. 또한 n개의 원소의 순서를 뒤섞는 순열의 개수는 n!와 같다. (nPr의 경우에는 n!/(n-r)! 이다.)

 

[1, 2, 3]

 

만약 리스트가 저렇게 주어졌을때, [1, 2, 3]에서 가능한 모든 순열을 리턴한다면 결과는 다음과 같다.

 

[
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [2, 3, 1],
    [3, 1, 2],
    [3, 2, 1]
]

 

순열 개수는 n!와 같으므로 3!를 하면 6이 나온다. 실제로 위의 개수를 세면 6개가 나온다.

 

이것을 python으로는 어떻게 구현하는지 알아보자!

 

 순열은 재귀함수를 이용하여 짤 수 있다.

    * DFS 관련 포스팅

[python] Graph Traversals(Search) 그래프 순회(탐색) 정리

 

DFS를 모른다면 위의 포스팅을 보고 아래를 보자.

 

def permute(nums) :
    results = []
    prev_elements = []
    
    def dfs(elements) :
        if len(elements) == 0 :
            results.append(prev_elements[:])
        
        for e in elements :
            next_elements = elements[:]
            next_elements.remove(e)
            
            prev_elements.append(e)
            dfs(next_elements)
            prev_elements.pop()
            
    dfs(nums)
    return results

print(permute([1, 2, 3])

 

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

 

이전 값을 하나씩 덧붙여 계속 재귀 호출을 진행하다보면 모든 원소가 붙게 된다.

 

이때 결과를 result에 넣어주고, [:]로 처리하는 이유는 일반적으로 prev_elements를 append로 넣으면 prev_elements가 변경되면 append로 넣은 값이 바뀌게 된다. 그래서 [:]로 넣어주고 copy()나 deepcopy()로 처리를 해주어도 된다.

 

def permute(nums, r) :
    results = []
    prev_elements = []
    
    def dfs(elements) :
        if len(elements) == (len(nums) - r) :
            results.append(prev_elements[:])
        
        for e in elements :
            next_elements = elements[:]
            next_elements.remove(e)
            
            prev_elements.append(e)
            dfs(next_elements)
            prev_elements.pop()
            
    dfs(nums)
    return results
 
print(permute([1,2,3],2))

 

[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

(len(nums) - r)을 해서 nPr 형태로 바꿀수도 있다.

 

순열을 구하는 방법에는 모듈을 사용하는 경우도 있다.

 

itertools 모듈은 반복자 생성에 최적화된 효율적인 기능을 제공한다.

 

https://python.flowdas.com/library/itertools.html

itertools --- 효율적인 루핑을 위한 이터레이터를 만드는 함수 — 파이썬 설명서 주석판

위 페이지에 들어가면 itertools에 있는 함수들을 구경할 수 있다.

 

우리는 여기서 순열을 찾자..!

 

import itertools
itertools.permutations()

 

이 함수를 이용하면 된다.

 

import itertools
print(list(itertools.permutations([1, 2, 3])))

 

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

 

import itertools
print(list(itertools.permutations([1, 2, 3],2)))

 

[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

 

이런식으로 사용하면 된다.. 단 출력값이 tuple이기 때문에 이것을 list형태로 바꾸고 싶다면..

 

 

import itertools
print(list(map(list,itertools.permutations([1, 2, 3]))))

 

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

 

이렇게 사용하면 된다.