순열 알고리즘

순열이란 영어로는 Permutation으로

 

n개의 물체를 순서를 고려해서 m개를 뽑는 경우의수를 의미합니다.

 

중고등학교 시간에 배웠던 nPm입니다.

 

n개중 m개를 고르는 순열의 경우의 수

경우의 수가 몇개인지 구하는 것은 간단합니다.

 

n!/m!을 해주면 갯수는 구할 수가 있습니다.

 

하지만 컴퓨터과학에서 모든 경우의수를 탐색하는 완전탐색을 위해서는

 

경우의 수의 갯수가 아니라, 모든 경우의 수를 구해야 하는 일이 있습니다.

 

1. Python의 내장라이브러리인 itertools의 permutations 매쏘드를 사용할 수 있습니다.

 

2. 직접 산출하는 함수를 지정하는 방법에 대해서 살펴봅시다.

 

일단 우리는 nPm의 경우의수 개수를 알고 있습니다.

 

해당 방법을 활용해서 경우의수를 모두 구하게 됩니다.

4P2의 경우의 수를 구하기 위한 재귀적인 접근방법의 추상화된 이미지

첫번째 Pick의 가능한 경우의 수는 nPm입니다.

 

이때 모든 Element가 동일한 개수를 가지므로

 

각 원소는 nPm/n의  => (n-1)P(m-1)개의 자기자신을 선두Element로 갖는 경우의수를 갖습니다.

 

이제, 경우의 수의 첫번째 Element의 배열이 모두 완료되었습니다.

 

이제는 각 선두Element값에 따라 부분배열을 분할하여 동일한 알고리즘을 반복해줍니다.

 

이렇게되면 각 부분배열 별로 정해진 경우의 수의 부분배열을 반환하고

 

Merge Sort의 개념과 비슷하게,

 

부분배열을 Merge하면서 최종적으로 모든 경우의수를 구하게 됩니다.

 

Python으로 구현해본 permutation 소스코드입니다 :)

#순열함수 구현을 위해서 Factorial 을 구하는 함수를 정의합니다.
def fact(n):
    result = 1
    #0! = 1로 정의되어있으므로, 예외처리를 합니다.
    if n == 0:
        return result
    #n의값을 1씩 줄이면서 곱하여 Factorial값을 구합니다.
    while True:
        result = n*result
        n = n-1
        if n<=0:
            break
    return result



def permut(data, n, result = 999):
	#함수 처음에는 모든 경우의수 개수만큼의 List를 만들어 줍니다.
	if result == 999:
        result = [[]for i in range(int(fact(len(data))/fact(len(data)-n)))]            

    n = n-1
    #n+1번째 자리의경우의수를 구하기 위한 경우의수를 계산합니다.    
    loop_count = int(fact(len(data)-1)/fact(len(data)-n-1))        
    #loop_count를 이용해서 n+1번째 자리에 가능한 경우의수를 채워넣습니다.
    for i in range(len(data)):
        for j in range(loop_count):                
            result[j+i*loop_count].append(data[i])        
    for i in range(len(data)):                        
    	#만약 n=0이라면, 더이상 경우의수가 없으므로 재귀함수를 종료시킵니다.
        if n == 0:
            break
        #아닐 경우에는 이제 n번째 값이 같고, n+1번째 자리에서 값이 같은부분배열을 만들어
        #permutation함수를 순환호출 시킵니다.
        else:
            result[(i)*loop_count:(i+1)*loop_count] = permut(data[:i]+data[i+1:], n,result[(i)*loop_count:(i+1)*loop_count])    
  	#순환호출이 모두 끝난 후 Merge된 모든 경우의수를 반환
    return result


permut(data = [7,9,6,1,2],n = 3)
Out[133]: 
[[7, 9, 6],
 [7, 9, 1],
 [7, 9, 2],
 [7, 6, 9],
 [7, 6, 1],
 [7, 6, 2],
 [7, 1, 9],
 [7, 1, 6],
 [7, 1, 2],
 [7, 2, 9],
 [7, 2, 6],
 [7, 2, 1],
 [9, 7, 6],
 [9, 7, 1],
 [9, 7, 2],
 [9, 6, 7],
 [9, 6, 1],
 [9, 6, 2],
 [9, 1, 7],
 [9, 1, 6],
 [9, 1, 2],
 [9, 2, 7],
 [9, 2, 6],
 [9, 2, 1],
 [6, 7, 9],
 [6, 7, 1],
 [6, 7, 2],
 [6, 9, 7],
 [6, 9, 1],
 [6, 9, 2],
 [6, 1, 7],
 [6, 1, 9],
 [6, 1, 2],
 [6, 2, 7],
 [6, 2, 9],
 [6, 2, 1],
 [1, 7, 9],
 [1, 7, 6],
 [1, 7, 2],
 [1, 9, 7],
 [1, 9, 6],
 [1, 9, 2],
 [1, 6, 7],
 [1, 6, 9],
 [1, 6, 2],
 [1, 2, 7],
 [1, 2, 9],
 [1, 2, 6],
 [2, 7, 9],
 [2, 7, 6],
 [2, 7, 1],
 [2, 9, 7],
 [2, 9, 6],
 [2, 9, 1],
 [2, 6, 7],
 [2, 6, 9],
 [2, 6, 1],
 [2, 1, 7],
 [2, 1, 9],
 [2, 1, 6]]