조합(Combination)

조합(Combination)

집합에서 원하는 개수의 원소를 선택하는 방법을 말한다. 선택된 원소들의 순서는 고려하지 않으며, 단순히 선택된 원소들의 조합을 구하는 것이다. 순서가 다르더라도 같은 원소를 포함하면 같은 조합으로 취급한다.

조합은 수학적으로 n개의 원소 중 r개를 선택하는 경우의 수를 구하는 것으로 표현된다. 이 때, 순서가 없으므로 조합의 경우의 수는 순열의 경우의 수보다 작다. nCr이라는 기호로 표현되며, 이는 n개의 원소 중 r개를 선택하는 경우의 수를 의미한다.

조합의 경우의 수는 다음과 같이 계산된다.

nCr = n! / (r! * (n-r)!)

n은 전체 원소의 개수, r은 선택할 원소의 개수를 의미한다.

조합은 중복을 허용하지 않는 조합과 중복을 허용하는 조합으로 나뉜다.
중복을 허용하지 않는 조합은 원소의 순서가 중요하지 않고, 한 번 선택된 원소는 다시 선택할 수 없는 경우의 수를 말한다. 예를 들어, 3개의 원소 {1, 2, 3} 중 2개를 선택하는 경우의 수는 {1, 2}, {1, 3}, {2, 3} 세 가지이다.

반면에, 중복을 허용하는 조합은 한 번 선택된 원소도 다시 선택할 수 있는 경우의 수를 말한다. 따라서 원소의 순서가 중요하지 않고, 중복을 허용하지 않는 조합보다 경우의 수가 더 많다. 예를 들어, 3개의 원소 {1, 2, 3} 중 2개를 선택하는 경우의 수는 {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3} 여섯 가지다.

중복을 허용하는 조합은 중복 조합, 중복 뽑기, 중복 선택 등으로 불리며, 대표적으로 복권 추첨, 랜덤 암호 생성 등에 사용된다. 반면에 중복을 허용하지 않는 조합은 순열, 조합, 로또 번호 추첨 등에 사용된다.

---

파이썬 코드

def combination(arr, r):
    result = []

    # 조합 생성 함수
    def generate(chosen):
        if len(chosen) == r:
            result.append(chosen[:])
            return

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

    generate([])
    return result

arr = [1, 2, 3]
r = 2
combinations = combination(arr, r)
print(combinations)

# [[1, 2], [1, 3], [2, 3]]

# itertools를 이용하면 간단하게 구할 수 있다.

import itertools

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

combinations = list(itertools.combinations(arr, r))
print(combinations)