[Algorithm] Backtracking(백트래킹) 순열 및 조합 구현하기 itertools

우선 순열과 조합의 차이를 알아보자.

순열 : 원소들의 순서를 고려하여 나열하는 것 (원소의 순서가 다르면 다른 순열로 취급)

조합 : 원소들의 순서를 고려하지 않고 나열하는 것 (선택된 원소의 순서는 고려되지 않음)

 

파이썬 라이브러리 중 하나인 itertools를 사용하면 조합과 순열을 쉽게 구할 수 있다.

from itertools import permutations, combinations

arr = [1,2,3]
k = 2

npr = list(permutations(arr, 2))
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

ncr = list(combinations(arr, 2))
# [(1, 2), (1, 3), (2, 3)]

 

그러나..

라이브러리를 사용하지 않고 백트래킹을 이용하여 구현해보자.

array = [1,2,3]
k = 2
used = [False for i in range(len(array))]

def backtrack_perm(arr):
    if len(arr)==k:
        print(arr, end=" ")
        return arr

    for i in range(len(array)):
        if used[i]==False:
            used[i] = True
            backtrack_perm(arr+[array[i]])
            used[i] = False

def backtrack_comb(idx, arr):
    if len(arr)==k:
        print(arr, end=" ")
        return arr

    for i in range(idx+1, len(array)):
        if used[i]==False:
            used[i] = True
            backtrack_comb(i, arr+[array[i]])
            used[i] = False

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

backtrack_comb(-1, [])
# [1, 2] [1, 3] [2, 3]

DFS 및 백트래킹에 요긴하게 쓰일 알고리즘...