순열과 조합 구현(순열, 조합, 중복순열, 중복 조합까지!) - 파이썬

개요

순열이란? : 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 나열한 것을 말합니다.
조합이란? : 서로 다른 n개의 원소에서 r개를 선택하는 경우를 말합니다.
중복순열이란? : 같은 종류의 수나 문자의 중복을 허용하는 순열을 말합니다.
중복조합이란? : 주어진 원소 가운데서 동일한 것의 중복을 허용하는 조합입니다.

구현방법

백트래킹을 이용하였습니다. 백트래킹이란 가지치기 방법으로 자신이 구하려는 해가 아닐 것 같다면 그 이후로는 가지 않고 이전으로 돌아가 해를 구하는 방법입니다.
여기서 중요한점은! DFS도 백트래킹을 이용한 하나의 알고리즘이라는 것!!! 이 글의 주제와는 많이 관련은 없으니 Pass!
결론: 재귀를 이용한 백트래킹을 이용!

1. 순열

첫번째로 순열! 순열을 만들 때 순열에서의 중복을 방지하기 위해서 visited배열을 이용한다!
코드

# 순열
# array: 배열, r: 순열의 길이, temp: 재귀에 사용할 순열의 중간값
def permutations(array, r, temp):
    if len(temp) == r:
        print(temp, end=' ')
        return
    else:
        for i in range(len(array)):
            if visited[i] == False:
                visited[i] = True
                permutations(array, r, temp + array[i])
                visited[i] = False

왜 백트래킹일까? - 백트래킹은 자신이 구하려는 해가 아닐 것 같다면 그 이후로는 가지 않는다고 했는데 위 코드를 살펴보면 순열에서 나열할 길이는 r로 temp의 길이가 r을 넘어선다면 더이상 재귀호출을 하지 않기 때문입니다. 결론적으로 구하려는 길이가 r을 넘어선다면 앞으로는 자신이 구하려는 해가 아닐 것이기에 이후로 가지 않습니다.

여기서 temp의 매개변수가 순열의 중간값을 저장하는데 temp의 변화과정을 살펴보겠습니다.

[1, 2, 3]이 저장되어있는 배열에서 길이 3의 순열을 만들 때의 변화의 모습을 도식화한 것입니다.

2. 조합

두번째는 조합입니다. 조합은 순열과 다르게 순서가 존재하지 않기 때문에 visited배열을 이용한 방문여부를 확인하지 않습니다.
코드

# 조합
# array: 배열, r: 조합 개수, temp: 중간값 저장, start: 재귀호출 시 시작할 인덱스
def combinations(array, r, temp, start):
    if len(temp) == r:
        print(temp, end=' ')
        return
    else:
    	# array배열에서 start인덱스부터 탐색을 한다.
        for i in range(start, len(array)):
            combinations(array, r, temp + array[i], i + 1)

3. 중복순열

세번째는 중복순열입니다. 중복순열은 순열과 원리는 같지만 순열에 중복값이 존재한다는 것입니다. 그렇기때문에 visited배열을 통한 방문여부는 체크하지 않습니다.

# 중복 순열
def overlap_permutations(array, r, temp):
    if len(temp) == r:
        print(temp, end=' ')
        return
    else:
        for i in range(len(array)):
            overlap_permutations(array, r, temp + array[i])

4. 중복조합

마지막으로는 중복조합입니다. 중복조합은 조합과 원리는 같지만 조합에 중복값이 존재한다는 것입니다.

# 중복 조합
def overlap_combinations(array, r, temp, start):
    if len(temp) == r:
        print(temp, end=' ')
    else:
    	# i : array배열에서의 인덱스라고 생각하면 됨
        for i in range(start, len(array)):
            overlap_combinations(array, r, temp + array[i], i)

4가지의 코드를 합쳐 1, 2, 3배열에 대하여 길이를 3만큼하여 함수들을 실행하게 되면

결과는 위와같이 나오게 됩니다! 학습을 위해 순열에서 temp매개변수의 변화를 도식화한것 처럼 도식화 해보는 방법 추천합니다!

• 파이썬에는 사실 itertools라는 라이브러리에 중복순열, 중복조합, 순열, 조합을 해주는 함수들이 존재합니다. 하지만 백트래킹을 학습하기 위해서 구현을 해보았고 실제로 도움이 많이 되었기에 파이썬을 이용하시더라도 한번씩 구현하고 생각해보면서 학습해보시는 것을 추천드립니다!