순열(Permutation)의 코드화

 

이전에 조합(Combination)의 코드화에 대해서 글을 작성한 적이 있었다.

이번에는 순열의 코드화에 대해 글을 적어보려한다.

 

순열의 코드화는 조합의 코드화에서 약간만 추가하면 쉽게 만들 수 있다.

 

 

[4, 3, 2, 1]에서 성분이 2개인 순열을 구하는 방식은 다음과 같다.

 

먼저 고정된 성분 4를 선택한다.

그 후, 고정된 성분 뒤의 배열에서 1개인 성분을 선택한다.

모두 돌았다면, 고정된 성분 4를 가장 뒤로 보낸다.

그 후 고정된 성분 3을 선택하고 위를 반복한다.

 

 

여기서 고정된 성분을 따로 떼어놓고 생각해보자.

고정된 성분 4를 제외하면, [3, 2, 1]에서 1개의 성분에 대한 순열을 구하는 것과 같다.

즉, list에서 성분이 n개인 순열을 구하는 방법은

고른 고정성분 앞의 배열을 고정 성분 뒤의 배열과 붙인 후 n-1개의 성분을

그 안에서 n-1개의 성분으로 이루어진 모든 순열을 구하고 앞에 고정된 성분을 붙이는 것과 같다.

 

이를 통해 순열의 알고리즘을 짜보자.

 

1. 고정된 성분을 선택

2. 고정된 성분 앞까지의 배열을 고정된 성분 뒤의 배열에 이은 후 이 배열에서 n-1개의 순열을 구함

3. 여기서 구해진 순열에 고정된 성분을 앞에 추가

4. 고정된 성분을 다음으로 넘기고 반복

 

이를 코드로 작성하면 다음과 같다

 

def permutation(list, count):
  if count == 1:
    return [[i] for i in list]
  
  permu_list = []
        
  for i in range(len(list)): #고정된 성분을 다음으로 넘기고 반복
    fix_element = list[i] #고정된 성분을 선택

    #고정된 성분 앞까지의 배열을 고정된 성분 뒤의 배열에 이은 후 
    #이 배열에서 n-1개의 순열을 구함
    for permu in permutation(list[i+1:] + list[:i], count - 1):
      permu_list.append([fix_element] + permu) # 여기서 구해진 순열에 고정된 성분을 앞에 추가
            
  return permu_list

 

 

Reference

조합의 코드화

Python 순열, 조합 구현하기