permutation 순열 만들기

permutation 이란 

순열이란 배치를 고려하여 순서를 구하는 방식을 의미한다. 앞에서 보았던 combination과는 순서를 생각하기 때문에 같은 조합갯수의 조합식을 뽑더라도 더 많은 갯수를 구해야만 한다. 

 

 

 python 라이브러리 itertools permutations

일단 누구나 쉽게 쓸수 있는 python 에서 제공하는 permutations 를 사용해보자 

from itertools import permutations

arr = [1,2,3,4]
nPr = permutations(arr, 1)
print(list(nPr))
nPr = permutations(arr, 2)
print(list(nPr))
nPr = permutations(arr, 3)
print(list(nPr))
nPr = permutations(arr, 4)
print(list(nPr))
'''
[(1,), (2,), (3,), (4,)]
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]
[(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), (1, 4, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1),
(2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 2, 4), (3, 4, 1), 
(3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)]
[(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), 
(2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), 
(3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1),
(4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]
'''

사용 방식은 아주 간단하다. permutation( arr, n) 사용하는 데이터 arr와 조합식을 만들고 싶은 갯 수 n을 입력하면 쉽게 구할 수 있다. 이제 재귀를 이용해서 한번 순열을 구해보자 

 

 재귀를 이용한 permutation 구하기 

우선 아래는 재귀를 활용한 순열 구하는 방법이다.

def permutation (numbers) :
    if len(numbers) <= 1 :
        return [numbers]
    
    result = []
    for i, num in enumerate( numbers ) :
        Temp = numbers.copy() 
        del Temp[i]
        rest = permutation(Temp)
        for _p in rest :
            result.append([ *_p, num])

    return result 

print(permutation([1,2,3,4]))
'''
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2],
[2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1],
[3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], 
[4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]
'''

이제 코드를 한번 분석해보자 

result = []
for i, num in enumerate( numbers ) :
  Temp = numbers.copy() 
  del Temp[i]
  rest = permutation(Temp)
  for _p in rest :
  	result.append([ *_p, num])

 

우선 위의 부분을 살펴 보자 numbers를 for문을 돌면서 현재 해당되는 원소를 del 시키고 이를 다시 permutation에 넣는 것을 확인 할 수 있다. 그리고 permutation으로 구한 행렬에 현재 원소를 추가해 결과를 만들어 내는 것을 확인 할 수 있다.

이전의 C( Combination )을 구할 때에는  C(N) = C(N-1) + C(N-1) U N으로 구했다면 

P (Permutation)은 P(N) =1 U P( N(1제외) ) + 2 U P( N(2제외)) ------ N U P( N(N제외) ) 이런 식으로 구하게 된다. 그래서 map을 활용한 최종 코드는 

def permutation(numbers) :
    if len(numbers) == 1 :
        return [numbers]
    
    result = []
    print(numbers)
    for _number in numbers : 
        Temp = numbers.copy()
        Temp.remove(_number)
        for _p in permutation( Temp ) :
            result.append([ *_p, _number])

    return result

위와 같은 형태를 뛰게 된다.