재귀 방법으로 순열과 조합 구현하기

순열과 조합의 차이는 순서에 상관이 있는지 없는지이다. 조합에서는 순서가 없기 때문에 시작점보다 작은 위치는 다시 방문하지 않는다. 그러나, 순열은 순서가 있기 때문에 시작점보다 작은 위치 또한 방문해야 한다.

라이브러리없이 구현하는 방법은 dfs 알고리즘을 이용하는 것인데, 그 중에도 재귀를 이용하여 구현할 수 있다.

 

 

순열(permutation)이란, 서로 다른 n개 중에서 순서에 상관하여 r개를 뽑는 경우의 수이다.

arr = [1, 2, 3, 4]
select = [False for _ in range(4)]
result = []


def dfs(cnt):
    if cnt == 3:
        print(*result)
        return
    for i in range(4):
        if not select[i]:
            select[i] = True
            result.append(arr[i])
            dfs(cnt + 1)
            result.pop()
            select[i] = False


dfs(0)

 

 

조합(combination)이란, 서로 다른 n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수이다.

arr = [1, 2, 3, 4]
select = [False for _ in range(4)]
result = []


def dfs(idx, cnt):
    if cnt == 3:
        print(*result)
        return
    for i in range(idx, 4):
        if not select[i]:
            select[i] = True
            result.append(arr[i])
            dfs(i + 1, cnt + 1)
            result.pop()
            select[i] = False


dfs(0, 0)