Python의 목록 조합

itertools.combinations()를 사용하면 입력 위치를 다시 선택하지 않고 정해진 개수의 항목을 고를 수 있습니다. 같은 위치를 여러 번 선택해도 된다면 itertools.combinations_with_replacement()를 사용하세요. 두 함수는 조합을 생성하므로 선택 순서가 달라도 새로운 결과로 보지 않습니다. 순열에서는 순서가 다른 선택을 서로 다른 결과로 취급합니다.

알맞은 조합 방식 선택하기

선택 개수를 고정하려면 combinations()를, 같은 위치를 반복해서 선택하려면 combinations_with_replacement()를 사용하세요. 모든 부분집합이 필요하다면 powerset() 함수를 만들 수 있습니다. 표준 라이브러리 함수는 튜플을 생성하는 이터레이터를 반환합니다. 입력은 값이 아니라 위치를 기준으로 처리되므로, 서로 다른 위치에 같은 값이 있으면 결과가 서로 똑같아 보일 수 있습니다. 결과 순서는 입력 위치의 순서를 따르며, 각 튜플 안의 값이 자동으로 정렬되지는 않습니다. 규칙을 직접 정의해야 한다면 재귀를 사용해 선택 과정을 명시적으로 구현할 수 있습니다.

itertools.combinations()로 중복 없이 선택하기

itertools.combinations(iterable, r)는 길이가 r인 튜플을 생성하며 같은 위치를 다시 선택하지 않습니다. 이터러블은 입력 순서대로 소비됩니다. 결과를 한꺼번에 저장하거나 살펴봐야 할 때는 이터레이터를 리스트로 변환하고, 그렇지 않으면 직접 순회하면 됩니다.

다음 예제를 실행해 보세요.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

from itertools import combinations

items = ["red", "blue", "green"]
for pair in combinations(items, 2):
    print(pair)

두 항목으로 이루어진 결과에서는 각 위치를 최대 한 번만 사용합니다. 개별 항목을 선택하려면 r을 1로 설정하고, 입력 전체를 하나의 튜플로 만들려면 r을 입력 위치의 개수로 설정하세요. r이 위치 개수보다 크면 이터레이터에 결과가 없습니다.

itertools.combinations_with_replacement()로 반복 선택하기

같은 입력 위치를 두 번 이상 선택해도 된다면 itertools.combinations_with_replacement(iterable, r)를 사용하세요. 이 함수도 길이가 r인 튜플을 생성하며, 위치 순서에 따른 규칙은 같습니다. 예를 들어 ["red", "blue"]에서 두 항목을 고르면 ("red", "red")와 ("blue", "blue")도 결과에 포함됩니다. combinations()는 이런 쌍을 생성하지 않습니다. 같은 맛을 두 스쿱 고르는 것처럼 반복 선택이 의미 있는 경우에 유용합니다. 인수 r은 여전히 모든 튜플의 길이를 결정합니다.

사용자 정의 구현에는 재귀나 제너레이터 사용하기

재귀 백트래킹 함수는 결과를 리스트에 모을 수 있습니다. 각 단계에서 값을 하나 추가하고 다음 위치부터 재귀 호출한 뒤, 그 값을 제거해 반복문이 다른 선택을 시도하도록 합니다. 제너레이터도 같은 선택 로직을 따르지만, 각 결과가 만들어지는 즉시 반환합니다. 호출하는 쪽에서 명시적으로 리스트로 변환하지 않는 한 결과 전체를 보관하지 않습니다. 그렇다고 본질적으로 더 빠른 것은 아닙니다.

아래 두 사용자 정의 함수는 r이 음수가 아닌 정수여야 하며, 그렇지 않으면 ValueError를 발생시킵니다. r = 0이면 두 함수 모두 빈 튜플 하나를 반환합니다. r이 양수이면서 입력 위치 개수보다 크면 어느 함수도 결과를 생성하지 않습니다. 제너레이터 함수의 본문은 지연 실행되므로, 제너레이터는 순회가 시작될 때 인수를 검사합니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

def get_combinations(items, r):
    if not isinstance(r, int) or isinstance(r, bool) or r < 0:
        raise ValueError("r must be a nonnegative integer")

    results = []

    def backtrack(start, chosen):
        if len(chosen) == r:
            results.append(tuple(chosen))
            return
        for index in range(start, len(items)):
            chosen.append(items[index])
            backtrack(index + 1, chosen)
            chosen.pop()

    backtrack(0, [])
    return results


def generate_combinations(items, r):
    if not isinstance(r, int) or isinstance(r, bool) or r < 0:
        raise ValueError("r must be a nonnegative integer")
    if r == 0:
        yield ()
        return
    for index in range(len(items)):
        for suffix in generate_combinations(items[index + 1 :], r - 1):
            yield (items[index],) + suffix


items = ["red", "blue", "green"]
print(get_combinations(items, 2))
print(list(generate_combinations(items, 2)))

지연 실행되는 사용자 정의 버전에서는 선택이 완성되는 지점에 yield를 사용하세요. 두 구현 모두 위치를 다시 선택하지 않도록 다음 재귀 호출의 인덱스를 index + 1로 넘겨야 합니다. 중복 값이 있다면 서로 다른 위치에서 나온 결과라도 똑같아 보일 수 있습니다.

powerset() 함수로 모든 부분집합 생성하기

멱집합에는 모든 크기의 부분집합이 들어가며, 빈 튜플과 입력 전체도 포함됩니다. 이 구현은 가능한 각 크기의 결과를 하나로 결합합니다. chain.from_iterable()은 이터레이터를 반환하므로, 모든 부분집합을 실제 리스트로 만들어야 할 때만 list()로 감싸세요.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

from itertools import chain, combinations


def powerset(items):
    values = list(items)
    return chain.from_iterable(
        combinations(values, size) for size in range(len(values) + 1)
    )


for subset in powerset(["red", "blue"]):
    print(subset)

입력 위치가 n개라면 멱집합에는 2**n개의 부분집합이 있습니다. 개수가 빠르게 늘어나므로 한 가지 크기의 선택만 필요할 때는 고정 크기의 조합 이터레이터를 사용하는 편이 좋습니다. 모든 크기의 부분집합이 실제 결과에 필요한 경우에 멱집합을 사용하세요.