[Algorithm] 재귀를 통한 순열(permutation) 구현(+ python 내장 함수 이용)

순열이란, N개의 원소에서 원하는 개수를 뽑을 때, 순서까지 고려하는 것을 말합니다.

 

예시)

[1, 2, 3] 배열에서 2개의 원소를 선택할 경우

=> (1, 2), (1, 3), (2, 3), (2, 1), (2, 3), (3, 1), (3, 2)

위와 같은 결과처럼 (1, 2), (2, 1)의 경우는 서로 다른 것으로 판단합니다.

🥸 재귀를 통한 코드 구현

test = [1, 2, 3]
test_len = len(test)

N = 2   # 뽑을 순열의 개수
visit = [0] * test_len # 해당 index의 값을 사용했는지 여부
arr = [0] * N   # 현재 순열을 담을 배열
arr_list = []   # 모든 순열을 담을 배열

def permutaion(level):
    if level >= N:	# 레벨이 N과 같은 경우(이미 N개의 원소를 선택한 경우)
        arr_list.append(arr[:]) # 얕은 복사를 통해서 현재 순열을 추가한다.
        return
    else:
        for i in range(test_len):
            if visit[i]: continue   # 이미 순열로 선택되었다면 통과
            visit[i] = 1	# 아직 선택되지 않은 경우이므로 선택처리
            arr[level] = test[i]    # 순열을 선택
            permutaion(level + 1)   # 재귀를 통해 반복
            visit[i] = 0    # 다음 트리로 내려가기 위해서 이전의 방문처리를 롤백

permutaion(0)	# 0개의 원소를 선택한 경우부터 시작
print(arr_list)

# 실행결과
>>> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

파이썬의 경우 내장함수를 통해서 더 쉽게 구현할 수 있습니다.

🥸 파이썬 내장함수 itertools.permutation을 통한 구현

import itertools

test = [1, 2, 3]
new_per = list(itertools.permutations(test, 2))	# test 배열에서 2개의 원소를 뽑아서 수열 생성 후 리스트로 변환
print(new_per)

# 실행결과
>>> [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]