n개의 원소 중 m개를 고르는 모든 방법: 세 가지 전략으로 Three ways to choose m of the n elements

이전 이항 계수 포스팅과도 연계될 수 있으나, 접근의 방법이 다릅니다.

[1, 2, 3, 4, 5] 중 세 개의 원소를 택하는 경우를 생각해 봅시다. 가능한 경우는

• [1, 2, 3]
• [1, 2, 4]
• [1, 2, 5]
• [1, 3, 4]
• [1, 3, 5]
• [1, 4, 5]
• [2, 3, 4]
• [2, 3, 5]
• [2, 4, 5]
• [3, 4, 5]

로 총 10가지(=$5 \choose 2$)입니다.

이를 Python을 이용해 구하는 코드는 다음과 같습니다.

n = 5

result = []
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            result.append((i, j, k))

그렇다면 만약 5개중 4개를 고른다면 어떻게 될까요? 아니면 임의의 개수($m$개)를 고른다면 이러한 for 문의 중첩으로 코드를 작성할 수 있을까요? 이는 불가능합니다.

따라서 이를 재귀로 풀이할 수 있습니다.

def choose(start, depth):
    if depth == 0:
        return None
    
    result = []
    for idx in range(start, n - depth + 1):
        recursed = choose(idx + 1, depth - 1)
        if recursed is None:
            result.append((idx, ))
        else:
            result += [(idx, ) + x for x in recursed]
    
    return result

또는 Python의 itertools 모듈의 내장 함수를 이용할 수도 있습니다 (이 경우 반환값은 리스트가 아닌 제너레이터입니다).

from itertools import combinations

result = combinations(range(n), 5)

대개 내장 함수를 이용한 방법이 가장 빠르고, Call Stack이나 불필요한 튜플 생성에 의해 중첩된 for의 방법이 재귀를 이용한 것보다 더 빠르나, 중첩 for 방법은 $m$을 임의로 정할 수 없다는 단점을 유의하시길 바랍니다.