[Python] 순열, 조합 구현하기

순열과 조합은 백트래킹을 이해하기 좋은 예제다. 파이썬은 유용한 라이브러리를 제공하기 때문에 간단하게 구현할 수 있지만 원리를 알고 사용하는 것과 모르고 사용하는 것은 분명한 차이가 있기에 포스팅을 남기고자 한다.

백트래킹이란? 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법. 최적화 문제와 결정 문제를 푸는 방법이다.

우선 본격적으로 들어가기 전, 설명의 편의를 위해 아래와 같이 가정을 한다.

N = 4
M = 3                    # N개중 M개 뽑기
list = [10, 20, 30, 40]  # 입력 배열
result = [0] * M         # 출력 배열
check = [False] * N      # 방문 확인 배열

라이브러리 사용해서

itertools 라이브러리를 사용하면 간단하게 순열과 조합을 구현할 수 있다. 해당 라이브러리를 사용해서 리턴되는 값의 타입은 튜플이며 직접 구현하는 것보다 속도도 더 빠르다고 한다.

순열

for i in itertools.permutations(list, M): # 일반 순열
    print(i, end=" ")

for i in itertools.product(list, repeat = M):  # 중복 순열
    print(i, end=" ")

조합

for i in itertools.combinations(list, M): # 일반 조합
    print(i, end=" ")

for i in itertools.combinations_with_replacement(list, M): # 중복 조합
    print(i, end=" ")

라이브러리 없이

순열

일반 순열 기준으로 설명하자면, 중복 체크를 위해 방문한 배열을 체크할 배열인 check가 필요하다. [1, 2, 3, 4] 중 3개를 뽑는 첫번째 경우인 123을 예를 들어보면 위와 같은 그림으로 이해할 수 있다. (중복 순열은 아래 코드의 코멘트 참고!)

def permutation(N, M, level):
    if level == M:
        print(result)
        return

    for i in range(N):
        if check[i] is False:
            check[i] = True  # 이 줄이랑~
            result[level] = list[i]
            permutation(N, M, level + 1)
            check[i] = False # ~ 이 줄 없으면 중복 허용

조합

조합은 중복 순열의 구현과 비슷하므로 그림은 생략한다. 매개변수가 순열이랑 좀 다른데, level은 순열과 동일하게 일반 조합 기준, idx는 중복을 제거하기 위함이다. (중복 조합은 아래 코드의 코멘트 참고!)

def combination(N, M, level, idx):
    if level == M:
        print(result)
        return

    for i in range(idx, N):
        result[level] = list[i]
        combination(N, M, level + 1, i + 1) # i+1 말고 i면 중복 허용

레퍼런스

• https://juhee-maeng.tistory.com/91
• https://www.crocus.co.kr/1240