자꾸 헷갈리는 순열(Permutation)과 조합(Combination)에 대한 수식을 정리해봤습니다.

먼저 순열과 조합의 수식을 알기 위해서는 팩토리얼부터 알고 가야 합니다.

팩토리얼

팩토리얼은 서로 다른 n개를 나열하는 경우의 수를 의미합니다.

\[n! = n(n-1)(n-2)(n-3)...1\]

순열

순열은 서로 다른 n개중에 순서에 의미를 두고 r개를 선택하는 경우의 수를 의미합니다.

\[nPr = {n! \over (n-r)!}\]

코드로 순열의 알고리즘을 구현하면 아래와 같습니다. (얼마든지 다른 형태로 구현 가능하지만 재귀를 이용한 구현 방식을 사용했습니다.)

def permutations(arr, n):
    # 1.
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generator(chosen, used):
        # 2.
        if len(chosen) == n:
            print(chosen)
            return

        # 3.
        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generator(chosen, used)
                used[i] = 0
                chosen.pop()
    generator([], used)

# 예제
# 1 ~ 5 중 3개를 선택한 순열 리스트를 출력
permutaions([1,2,3,4,5], 3)

조합

조합은 서로 다른 n개중에 순서 상관없이 r개를 선택하는 경우의 수를 의미합니다.

\[nCr = {n! \over (n-r)!r! }\]

코드로 조합의 알고리즘을 구현하면 다음과 같습니다. (얼마든지 다른 형태로 구현 가능하지만 재귀를 이용한 구현 방식을 사용했습니다.)

def combinations(arr, n):
    # 1.
    arr = sorted(arr)

    # 2.
    def generator(chosen):
        if len(chosen) == n:
            print(chosen)
            return

        # 3.
        start = arr.index(chosen[-1]) + 1 if chosen else 0
        for _next in range(start, len(arr)):
            chosen.append(arr[_next])
            generator(chosen)
            chosen.pop()
    generator([])

# 예제
# 1 ~ 5 중 3개를 선택한 조합 리스트 출력
combinations([1,2,3,4,5], 3)

중복 순열

중복 순열은 중복 가능한 n개 중에서 순서에 의미를 두고 r개를 선택하는 경우의 수를 의미합니다.

\[{n\Pi r} = n^r\]

중복 순열의 경우 중복되는 원소에 등장 순서를 정하면 해결할 수 있습니다.

일반 순열 코드와 동일하지만 # 3. 의 조건문만 달라집니다.

  1. i가 0일 때
    • i가 0이면 배열의 첫 원소이기 때문에 바로 사용
  2. arr[i-1] ≠ arr[i]일 때
    • arr은 정렬된 상태
    • 이 때 i번째 원소가 i-1번째와 다르면 다른 원소
  3. used[i-1]일 때
    • and 조건이 not used[i]이기 때문에 used[i-1]를 이용

위의 3가지 조건을 사용하면 중복된 원소를 피해서 순열을 생성할 수 있습니다.

def permutations(arr, n):
    # 1.
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generator(chosen, used):
        # 2.
        if len(chosen) == n:
            print(chosen)
            return

        # 3.
        for i in range(len(arr)):
            if not used[i] and (i == 0 or arr[i-1] != arr[i] or used[i-1]):
                chosen.append(arr[i])
                used[i] = 1
                generator(chosen, used)
                used[i] = 0
                chosen.pop()
    generator([], used)

# 예제
# 1 ~ 3 중 3개를 선택한 순열 리스트를 중복 요소 건너뛰고 출력
permutations([1,1,2,2,3], 3)

중복 조합

중복 조합은 중복 가능한 n개 중에서 순서 상관없이 r개를 선택하는 경우의 수를 의미합니다.

\[nHr = {_{n+r-1}C_r}\]

중복 조합 역시 중복 순열과 같은 조건을 추가하면 됩니다.

def combinations(arr, n):
    # 1.
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    # 2.
    def generator(chosen):
        if len(chosen) == n:
            print(chosen)
            return

        # 3.
        start = arr.index(chosen[-1]) + 1 if chosen else 0
        for _next in range(start, len(arr)):
            if used[_next] == 0 and (_next == 0 or arr[_next-1] != arr[_next] or used[_next-1]):
                chosen.append(arr[_next])
                used[_next] = 1
                generator(chosen)
                used[_next] = 0
                chosen.pop()
    generator([])

# 예제
# 1 ~ 3 중 3개를 선택한 조합 리스트를 중복 요소 건너뛰고 출력
combinations([1,1,2,2,3], 3)