경우의 수 - 순열·조합·비둘기집

이 장에서 배우는 것

기능을 만들다 보면 “가능한 입력은 몇 개인가”, “테스트를 전부 만들 수 있는가”, “서로 다른 값이 같은 저장 위치에 들어갈 수 있는가”라는 질문을 만난다. 이 질문에 답하려면 먼저 무엇을 서로 다른 경우로 셀지 정해야 한다. 같은 두 사람을 골라도 담당 순서가 다르면 다른 경우인지, 같은 옵션을 여러 번 골라도 되는지에 따라 답이 달라진다.

앞 장에서 입력과 출력을 연결하는 관계와 함수를 살펴보았다. 이번에는 연결이 만들어 낼 수 있는 경우의 수를 센다. 작은 입력을 Python으로 모두 만들어 보고, 그 개수와 계산식의 결과를 비교한다. 식을 먼저 외우기보다 코드가 어떤 결과를 만들고 무엇을 빠뜨리는지 확인하는 방식으로 진행한다.

• 여러 선택을 이어 붙일 때와 여러 묶음을 합칠 때의 계산을 구별한다.
• 순서와 중복 허용 여부를 기준으로 순열과 조합을 선택한다.
• 작은 입력을 모두 생성하여 공식의 조건과 경계값을 확인한다.
• 비둘기집 원리로 해시 충돌이 반드시 생기는 조건을 설명한다.

문제 상황

작업 예약 기능의 테스트를 준비한다고 하자. 실행 지역은 두 곳이고 실행 모드는 세 가지다. 모든 지역에서 모든 모드를 사용할 수 있다면 테스트할 설정은 여섯 개다. 여기에 담당자 세 명 중 두 명을 골라야 한다. 첫 번째 사람이 작업을 시작하고 두 번째 사람이 검토한다면 두 사람의 순서가 중요하다. 단순히 공동 담당자 두 명을 정한다면 순서는 중요하지 않다.

재시도 설정에서는 같은 실행 모드를 두 번 선택할 수도 있다. 반면 한 작업의 시작 담당자와 검토 담당자는 서로 달라야 한다고 정할 수 있다. “두 개를 고른다”라는 말만으로는 경우의 수를 계산할 수 없는 이유다. 선택 대상, 선택 횟수, 순서, 같은 대상의 재선택 가능 여부가 함께 필요하다.

작업 번호를 저장 칸 세 개에 나누는 문제도 있다. 번호를 3으로 나눈 나머지를 칸 번호로 쓰면 0번과 3번 작업은 같은 칸으로 간다. 이 현상이 프로그램의 실수인지, 저장 칸 수 때문에 피할 수 없는 일인지도 구별해야 한다. 먼저 작은 선택 문제부터 코드로 만들어 보자.

선택을 이어 붙이거나 합쳐서 세기

곱의 법칙: 각 선택 뒤에 몇 가지가 붙는가

지역 하나를 선택한 뒤 모드 하나를 선택한다고 하자. 지역마다 가능한 모드가 세 개라면, 지역 두 개에서 각각 세 개씩 설정이 나온다. 따라서 전체 개수는 2 × 3 = 6이다. 전공 수업에서는 이렇게 여러 단계의 선택을 이어 붙여 세는 규칙을 곱의 법칙이라고 부른다.

Python의 표준 라이브러리 모듈인 itertools는 여러 선택을 차례로 만들어 주는 도구를 제공한다. 모듈은 관련 기능을 모아 놓은 코드 묶음이다. product는 각 입력에서 원소를 하나씩 골라 묶는다. 여기서 만들어지는 ("동쪽", "빠름") 같은 값은 여러 값을 순서대로 묶은 튜플이다. 리스트와 비슷하게 값을 담지만, 만들어진 뒤 각 자리의 값을 바꾸지 않는다.

from itertools import product

regions = ["동쪽", "서쪽"]
modes = ["빠름", "보통", "절약"]
settings = list(product(regions, modes))

assert len(settings) == 2 * 3
assert ("동쪽", "빠름") in settings

list로 감싸면 생성되는 묶음을 리스트에 모두 담는다. assert는 뒤의 조건이 참인지 검사한다. 거짓이면 실행을 멈추므로, 예상과 실제가 어긋나는 지점을 찾는 데 쓸 수 있다. 이 예에서는 두 조건이 모두 참이므로 출력 없이 끝난다.

곱셈에 필요한 조건은 각 단계에서 이어지는 선택의 개수가 일정하다는 것이다. 지역에 따라 모드의 이름이 달라도 개수가 같으면 곱해서 셀 수 있다. 그러나 동쪽에서는 세 모드, 서쪽에서는 두 모드만 허용한다면 2 × 3을 쓰면 안 된다. 아래 코드는 그 작은 반례다.

allowed = {
    "동쪽": ["빠름", "보통", "절약"],
    "서쪽": ["보통", "절약"],
}
settings = [
    (region, mode)
    for region in allowed
    for mode in allowed[region]
]

assert len(settings) == 3 + 2
assert len(settings) != 2 * 3

대괄호 안에서 반복과 결과식을 함께 쓰는 표기를 리스트 내포라고 한다. 위 코드는 지역을 하나씩 꺼낸 뒤 그 지역에서 허용하는 모드만 순회한다. 모든 조합을 만든 뒤 금지된 것을 지우는 대신, 처음부터 허용된 경우만 만든 셈이다.

합의 법칙: 같은 결과를 두 번 세지 않는가

긴급 작업 두 개와 일반 작업 세 개 중 하나를 처리한다고 하자. 두 묶음에 같은 작업이 없다면 선택지는 2 + 3 = 5개다. 전공 수업에서는 서로 겹치지 않는 경우를 합쳐 세는 규칙을 합의 법칙이라고 부른다. 여기서 “겹치지 않는다”는 조건이 핵심이다.

urgent = {"긴급A", "긴급B"}
normal = {"일반A", "일반B", "일반C"}

assert len(urgent | normal) == len(urgent) + len(normal)

manual = {"작업A", "공통"}
scheduled = {"공통", "작업B"}

assert len(manual | scheduled) == 3
assert len(manual) + len(scheduled) == 4

|는 두 집합의 원소를 합친다. 같은 값은 한 번만 남긴다. 두 번째 예에서 “공통”은 양쪽에 있으므로 단순히 크기를 더하면 두 번 센다. 실제 개수는 2 + 2 − 1 = 3이다. 두 묶음의 크기를 더한 뒤 겹친 부분의 크기를 한 번 빼는 계산을 전공 수업에서는 포함과 배제의 원리라고 부른다. 여기서는 두 묶음의 경우만 사용한다.

같은 작업이라도 “수동 실행 요청”과 “예약 실행 요청”을 서로 다른 대상으로 셀 때는 요청 경로를 값에 포함해야 한다. 경우의 수를 세기 전에 무엇의 동일성을 판단하는지 정해야 한다. 값만 세는 코드와 실행 요청을 세는 코드는 같은 질문에 답하지 않는다.

순서와 중복으로 순열·조합 고르기

순열: 자리가 다르면 결과도 다르다

담당자 가, 나, 다 중 시작 담당자와 검토 담당자를 한 명씩 정한다. 한 사람이 두 역할을 맡을 수 없다면 첫 자리에는 세 명, 다음 자리에는 남은 두 명이 올 수 있다. 따라서 3 × 2 = 6가지다. 전공 수업에서는 서로 다른 대상 중 일부를 골라 순서 있게 나열하는 것을 순열(permutation)이라고 부른다.

from itertools import permutations

people = ["가", "나", "다"]
assignments = list(permutations(people, 2))

assert len(assignments) == 6
assert ("가", "나") in assignments
assert ("나", "가") in assignments
assert ("가", "가") not in assignments

서로 다른 대상 n개 중 r개를 중복 없이 순서 있게 고르면 n × (n − 1) × … × (n − r + 1)가지다. n!은 1부터 n까지의 정수를 곱한 값이며, 전공 수업에서는 계승(factorial)이라고 부른다. 이를 쓰면 순열의 개수는 n! / (n − r)!이다. Python에서는 math.perm(n, r)으로 계산한다.

n개를 모두 나열하면 n!가지다. 한편 아무것도 고르지 않는 방법은 빈 결과 하나다. 이 계산을 일관되게 표현하도록 0!은 1로 정한다. 아래 검사는 빈 결과가 실제로 한 번 만들어지는지 확인한다.

from itertools import permutations
from math import factorial, perm

assert len(list(permutations(["가", "나", "다"]))) == factorial(3)
assert list(permutations(["가", "나", "다"], 0)) == [()]
assert perm(3, 0) == 1

조합: 순서를 지우면 몇 개가 남는가

같은 세 명 중 공동 담당자 두 명을 고른다면 가와 나를 고르는 것과 나와 가를 고르는 것은 같다. 전공 수업에서는 이렇게 순서를 구별하지 않고 고르는 것을 조합(combination)이라고 부른다. combinations는 입력에 놓인 순서를 기준으로 각 선택을 한 번씩만 만든다.

from itertools import combinations
from math import comb

teams = list(combinations(["가", "나", "다"], 2))

assert teams == [("가", "나"), ("가", "다"), ("나", "다")]
assert len(teams) == comb(3, 2) == 3

서로 다른 r개를 골랐다면, 그 원소를 나열하는 순서는 r!가지다. 순열에서는 그 순서를 모두 따로 세었으므로 r!로 나누면 순서를 구별하지 않는 개수가 된다. 조합의 개수는 n! / (r! × (n − r)!)이다. 위 예에서는 여섯 순열을 두 개씩 묶어 세 조합을 얻는다.

공식에서 나눗셈이 보인다고 Python의 /로 직접 계산할 필요는 없다. /는 소수 부분을 표현할 수 있는 부동소수점 수를 만든다. 개수가 커지면 정수의 모든 자릿수를 그대로 표현하지 못할 수 있다. 개수를 구하는 목적에는 정수를 돌려주는 comb와 perm이 알맞다.

중복: 같은 대상을 다시 고를 수 있는가

세 모드 중 하나를 첫 실행에, 하나를 두 번째 실행에 배정하자. 같은 모드를 두 번 써도 된다면 각 자리의 선택지는 계속 세 개다. 전체는 3 × 3 = 9가지다. 전공 수업에서는 같은 대상을 다시 고르면서 순서를 구별하는 선택을 중복순열이라고 부른다. r개 자리마다 n개를 고를 수 있으면 n의 r제곱이며, Python에서는 n ** r로 쓴다.

from itertools import product, combinations_with_replacement

modes = ["빠름", "보통", "절약"]
plans = list(product(modes, repeat=2))
bundles = list(combinations_with_replacement(modes, 2))

assert len(plans) == 3 ** 2 == 9
assert ("빠름", "빠름") in plans
assert len(bundles) == 6

순서를 구별하지 않으면서 같은 대상을 여러 번 고르면 중복조합이라고 부른다. 예를 들어 모드 이름이 붙은 설정권 두 장을 모으는 경우다. “빠름 한 장과 보통 한 장”은 담은 순서와 관계없이 같은 묶음이다. combinations_with_replacement는 이런 묶음을 생성한다.

중복조합의 개수도 작은 배치 문제로 바꿀 수 있다. 세 종류에서 두 개를 고른 결과를 종류별 개수로 쓰면, 합이 2인 세 개의 음이 아닌 정수다. 선택한 개수를 표시하는 점 두 개와 종류의 경계를 표시하는 막대 두 개를 나열해 보자. ●|●|는 첫 종류 하나, 둘째 종류 하나, 셋째 종류 영 개를 뜻한다. 네 자리 중 점 두 개의 위치를 고르면 되므로 6가지다.

일반적으로 n이 1 이상이면 점 r개와 경계 n − 1개가 필요하다. 따라서 전체 n + r − 1자리에서 점 r개의 위치를 고르는 comb(n + r - 1, r)이 중복조합의 개수다. 대상이 아예 없는 경우에는 이 식을 그대로 쓰지 않는다. 대상이 없어도 영 개를 고르는 결과는 빈 묶음 하나이며, 하나 이상 고르는 결과는 없다.

서로 다른 대상 n개에서 r개를 고를 때의 네 가지 기준

선택 방식	순서	같은 대상 재선택	개수와 도구
순열	구별한다	허용하지 않는다	perm(n, r), permutations
조합	구별하지 않는다	허용하지 않는다	comb(n, r), combinations
중복순열	구별한다	허용한다	n ** r, product
중복조합	구별하지 않는다	허용한다	comb(n + r - 1, r), combinations_with_replacement

이 표에서 중복 없는 선택의 계승 표현은 0 ≤ r ≤ n을 전제로 한다. Python의 perm과 comb은 음이 아닌 정수 n, r에 대해 r이 n보다 크면 0을 반환한다. 음수를 “선택할 수 없음”의 표시로 넣지는 않는다. 중복조합 공식은 앞서 설명한 대로 n ≥ 1을 전제로 한다.

비둘기집 원리로 해시 충돌 이해하기

저장 칸이 세 개인데 값 네 개를 모두 넣어야 한다면, 어느 칸에는 두 개 이상 들어간다. 각 칸에 하나 이하만 들어 있다고 가정하면 전체 값이 세 개 이하여야 하므로 네 개를 넣었다는 조건과 맞지 않는다. 전공 수업에서는 이처럼 대상 수가 칸 수보다 많으면 같은 칸을 공유하는 대상이 있다는 사실을 비둘기집 원리(pigeonhole principle)라고 부른다.

값을 정해진 범위의 번호로 바꾸는 함수를 해시 함수(hash function)라고 한다. 서로 다른 두 값이 같은 해시 결과를 얻는 현상은 해시 충돌(hash collision)이다. 여기서는 작업 번호를 3으로 나눈 나머지를 저장 칸 번호로 쓰는 단순한 함수를 만든다. %는 나눗셈의 나머지를 구하는 연산자다.

keys = [0, 3, 1, 4]
buckets = [[] for _ in range(3)]

for key in keys:
    buckets[key % 3].append(key)

assert buckets == [[0, 3], [1, 4], []]
assert any(len(bucket) > 1 for bucket in buckets)

저장 위치별로 값을 모은 칸을 버킷이라고 부른다. [[] for _ in range(3)]는 서로 다른 빈 리스트 세 개를 만든다. 밑줄은 반복 변수의 값을 사용하지 않겠다는 관례적 이름이다. any는 전달받은 조건 중 하나라도 참이면 참을 반환한다. 따라서 마지막 줄은 값이 두 개 이상인 칸이 있는지 확인한다.

이 원리는 충돌이 생기는 정확한 위치를 알려 주지 않는다. 또 값이 칸보다 적으면 충돌하지 않는다는 뜻도 아니다. 예를 들어 값이 0과 3 두 개뿐이어도 두 값의 나머지는 모두 0이다. “칸보다 많으면 반드시 충돌한다”와 “칸보다 적으면 충돌하지 않는다”는 서로 다른 주장이다.

assert 0 % 3 == 3 % 3
assert len({0, 3}) <= 3

더 넓게 보면 값 N개를 칸 m개에 넣을 때 적어도 한 칸에는 N / m을 올림한 수 이상의 값이 들어간다. 올림은 소수 부분이 있으면 다음 정수로 높이는 것이다. 양의 정수에서는 (N + m - 1) // m으로 계산할 수 있다. //는 이 경우 나눈 몫의 정수 부분을 구한다. N이 4이고 m이 3이면 적어도 한 칸에 두 개가 들어간다. 뒤의 완성 코드에서도 이 하한을 검사한다.

실무에서 만나는 곳

옵션별 테스트를 만들 때는 곱의 법칙으로 전체 규모를 먼저 가늠할 수 있다. 참과 거짓을 고르는 옵션 열 개만 있어도 설정은 2의 10제곱인 1,024개다. 실제 실행 코드에 금지된 설정이 있다면 전체 곱에서 끝내지 말고 허용 조건을 반영해야 한다. 담당 순서나 처리 순서가 결과를 바꾸는 테스트에는 순열을, 구성원만 중요한 테스트에는 조합을 쓴다.

해시 기반 저장 구조에서는 충돌 가능성을 고려해 같은 칸의 여러 값을 구분할 방법이 필요하다. 이번 예제는 버킷에 원래 값을 함께 보관한다. 실제 구조에서도 같은 칸 번호를 얻었다는 사실만으로 원래 값까지 같다고 판단해서는 안 된다. 유한한 범위의 요약값으로 더 많은 입력을 구별하려 하면 충돌을 피할 수 없다는 것이 비둘기집 원리가 주는 결론이다.

충돌이 반드시 생기는 조건과 충돌이 얼마나 자주 생기는지는 다른 질문이다. 여기서는 반드시 성립하는 개수 관계까지만 확인한다. 다음 장에서는 가능한 결과 중 어떤 일이 일어날 가능성을 수로 나타내는 방법을 다룬다.

완성 코드

아래 내용을 main.py로 저장한다. 생성한 경우의 수와 공식을 비교하고, 빈 선택과 해시 충돌의 경계도 함께 검사한다. 작은 입력만 사용하며 외부 패키지, 네트워크, 난수를 사용하지 않는다. Python 3.12 이상에서 같은 출력으로 바로 끝난다.

from itertools import (
    combinations,
    combinations_with_replacement,
    permutations,
    product,
)
from math import comb, factorial, perm


def count_cases(cases):
    return sum(1 for _ in cases)


def check(label, actual, expected):
    assert actual == expected, (label, actual, expected)
    print(f"{label}: 생성={actual}, 공식={expected}")


def main():
    regions = ["동쪽", "서쪽"]
    modes = ["빠름", "보통", "절약"]
    people = ["가", "나", "다"]
    n = len(people)
    r = 2

    check("곱의 법칙", count_cases(product(regions, modes)), 2 * 3)

    urgent = {"긴급A", "긴급B"}
    normal = {"일반A", "일반B", "일반C"}
    assert not (urgent & normal)
    check("합의 법칙", len(urgent | normal), len(urgent) + len(normal))

    manual = {"작업A", "공통"}
    scheduled = {"공통", "작업B"}
    check(
        "겹치는 두 묶음",
        len(manual | scheduled),
        len(manual) + len(scheduled) - len(manual & scheduled),
    )

    check("전체 순열", count_cases(permutations(people)), factorial(n))
    check("순열", count_cases(permutations(people, r)), perm(n, r))
    check("조합", count_cases(combinations(people, r)), comb(n, r))
    check("중복순열", count_cases(product(people, repeat=r)), n ** r)
    check(
        "중복조합",
        count_cases(combinations_with_replacement(people, r)),
        comb(n + r - 1, r),
    )
    check("빈 선택", count_cases(combinations(people, 0)), comb(n, 0))
    check("인원 초과", count_cases(permutations(people, 4)), perm(n, 4))

    assert list(product([], repeat=0)) == [()]
    assert list(combinations_with_replacement([], 0)) == [()]
    assert list(combinations_with_replacement([], 1)) == []

    keys = [0, 3, 1, 4]
    bucket_count = 3
    assert len(keys) == len(set(keys))
    assert len(keys) > bucket_count
    buckets = [[] for _ in range(bucket_count)]
    for key in keys:
        buckets[key % bucket_count].append(key)

    lower_bound = (len(keys) + bucket_count - 1) // bucket_count
    assert max(len(bucket) for bucket in buckets) >= lower_bound
    assert any(len(bucket) > 1 for bucket in buckets)
    assert 0 % bucket_count == 3 % bucket_count
    print(f"버킷: {buckets}")
    print(f"한 버킷의 최소 보장 개수: {lower_bound}")
    print(f"칸보다 적어도 충돌: {0 % bucket_count == 3 % bucket_count}")


if __name__ == "__main__":
    main()

줄별 해설

from itertools import (...) 부분은 경우를 생성하는 네 함수를 가져온다. 괄호를 사용하면 가져올 이름을 여러 줄에 나누어 적을 수 있다. math에서 가져온 세 함수는 경우를 생성하지 않고 정수 개수만 계산한다. 두 종류의 도구를 나란히 사용해 생성 결과와 공식을 비교한다.

count_cases의 sum(1 for _ in cases)는 결과를 하나 꺼낼 때마다 1을 더한다. 괄호 안에서 필요할 때마다 값을 내놓는 표현을 생성기 표현식이라고 한다. 모든 결과를 리스트에 보관하지 않고도 개수를 셀 수 있다. 다만 모든 경우를 실제로 방문하므로 경우의 수가 많으면 시간은 오래 걸린다.

check는 실제 개수와 예상 개수가 같은지 검사한 뒤 한 줄로 출력한다. assert 뒤의 쉼표 다음 값은 검사가 실패했을 때 확인할 정보다. f"..."는 중괄호 안의 계산 결과를 문자열에 넣는 표기다. 여기서는 검사 이름과 두 개수를 출력한다.

main은 프로그램의 작업을 모은 함수다. n은 선택 가능한 사람 수, r은 고를 사람 수다. 곱의 법칙 검사에서는 지역과 모드를 묶는다. 합의 법칙 검사 앞의 assert not (urgent & normal)은 교집합이 비었는지 확인한다. 빈 집합은 조건식에서 거짓으로 취급되므로 not을 붙이면 참이 된다.

“겹치는 두 묶음” 검사에서는 합집합의 실제 크기를 구한 뒤, 두 크기의 합에서 교집합 크기를 뺀 값과 비교한다. 이어지는 다섯 검사는 전체 순열부터 중복조합까지 같은 세 사람을 대상으로 실행한다. “빈 선택”은 아무도 고르지 않는 경우가 하나임을, “인원 초과”는 세 명에서 서로 다른 네 명을 나열할 수 없음을 확인한다.

빈 입력을 사용하는 세 검사는 일반 공식의 적용 범위를 보완한다. repeat=0은 자리가 없다는 뜻이므로 빈 튜플 하나가 나온다. 중복조합에서도 영 개 선택은 가능하지만, 없는 대상 중 하나를 고를 수는 없다.

해시 검사에서는 set(keys)로 중복 값을 없앤 뒤 원래 길이와 비교한다. 이 조건으로 서로 다른 키 네 개를 사용하고 있음을 확인한다. 각 키를 나머지가 가리키는 버킷에 추가하고, 가장 많은 값이 든 버킷의 크기를 max로 구한다. 그 크기가 올림으로 계산한 하한 이상인지 검사한다. 마지막 조건문은 이 파일을 직접 실행할 때 main을 호출하는 표준적인 진입점 표기다.

실행 결과

파일이 있는 디렉터리에서 다음 명령을 실행한다.

python3 main.py

예상 출력은 다음과 같다. 집합 자체를 출력하지 않으므로 집합 원소의 표시 순서에 영향을 받지 않는다.

곱의 법칙: 생성=6, 공식=6
합의 법칙: 생성=5, 공식=5
겹치는 두 묶음: 생성=3, 공식=3
전체 순열: 생성=6, 공식=6
순열: 생성=6, 공식=6
조합: 생성=3, 공식=3
중복순열: 생성=9, 공식=9
중복조합: 생성=6, 공식=6
빈 선택: 생성=1, 공식=1
인원 초과: 생성=0, 공식=0
버킷: [[0, 3], [1, 4], []]
한 버킷의 최소 보장 개수: 2
칸보다 적어도 충돌: True

마지막 줄은 전체 키 네 개와 별도로, 키 두 개 0과 3만 보아도 충돌한다는 사실을 출력한다. 작은 예에서 공식과 생성 결과가 일치한다고 모든 입력에 대한 증명이 끝나는 것은 아니다. 앞에서 살펴본 자리별 선택 수와 중복 계산의 이유가 일반적인 근거이고, 실행 검사는 구현과 이해가 맞물리는지 확인하는 수단이다.

실무에서 자주 틀리는 것

순서가 있는 역할에 조합을 쓰는 경우

시작 담당자와 검토 담당자를 정하면서 조합을 쓰면 역할을 뒤집은 배치를 빠뜨린다. 아래의 틀린 코드는 실행은 되지만 질문과 다른 결과를 센다.

from itertools import combinations

people = ["가", "나", "다"]
wrong = list(combinations(people, 2))
assert len(wrong) == 3

역할을 튜플의 첫 자리와 둘째 자리에 대응시킨 뒤 순열로 생성한다. 반대로 역할 구별이 없는 팀을 세는 목적이라면 조합이 맞다.

from itertools import permutations

people = ["가", "나", "다"]
fixed = list(permutations(people, 2))
assert len(fixed) == 6
assert ("가", "나") in fixed and ("나", "가") in fixed

겹치는 결과를 그대로 더하는 경우

서로 다른 필터의 결과를 더할 때는 같은 항목이 양쪽에 잡힐 수 있다. 단순 합은 필터에 걸린 횟수를 셀 수는 있어도 서로 다른 항목 수와 같지는 않다.

left = {"A", "공통"}
right = {"공통", "B"}
wrong = len(left) + len(right)
assert wrong == 4

서로 다른 항목 수를 원한다면 합집합을 사용한다. 계산식으로 확인할 때는 겹친 부분을 한 번 뺀다.

left = {"A", "공통"}
right = {"공통", "B"}
fixed = len(left | right)
assert fixed == len(left) + len(right) - len(left & right)
assert fixed == 3

입력의 같은 값을 자동으로 합쳐 줄 것이라 생각하는 경우

itertools의 순열과 조합은 값의 동일성으로 입력을 합치지 않는다. 입력의 각 위치를 선택 대상으로 삼는다. 따라서 같은 값이 여러 위치에 있으면 같은 값의 결과가 여러 번 나온다.

from itertools import permutations

labels = ["가", "가", "나"]
wrong = list(permutations(labels, 2))
assert len(wrong) == 6
assert wrong.count(("가", "나")) == 2

서로 다른 이름만 대상으로 삼으려는 의도라면 먼저 중복 이름을 제거한다. sorted는 결과를 정렬한 리스트로 만들어 뒤의 생성 순서도 일정하게 한다. 같은 이름을 가진 서로 다른 사람을 세는 문제라면 이름을 합치지 말고 각 사람을 구분할 번호를 사용해야 한다.

from itertools import permutations

labels = ["가", "가", "나"]
unique_labels = sorted(set(labels))
fixed = list(permutations(unique_labels, 2))
assert fixed == [("가", "나"), ("나", "가")]

칸이 충분하면 충돌도 없다고 판단하는 경우

다음 조건은 충돌 검사로 쓸 수 없다. 키 개수와 칸 개수만 비교하며 실제 배치를 보지 않기 때문이다.

keys = [0, 3]
bucket_count = 3
wrong_no_collision = len(keys) <= bucket_count
assert wrong_no_collision is True

해당 입력의 충돌 여부는 각 키가 어느 칸으로 가는지 확인해야 한다. 서로 다른 키를 전제로 하면, 만들어진 칸 번호의 종류가 키 개수보다 적을 때 충돌이 있다.

keys = [0, 3]
bucket_count = 3
assert len(keys) == len(set(keys))
used_buckets = {key % bucket_count for key in keys}
has_collision = len(used_buckets) < len(keys)
assert has_collision is True

한눈에 보기

경우의 수를 계산하기 전에 확인할 질문

질문	판단 기준	작은 확인 방법
선택을 이어 붙이는가	각 단계의 선택 수가 일정하면 곱한다	product로 모두 생성한다
여러 묶음 중 하나를 고르는가	겹치지 않으면 크기를 더한다	교집합이 비었는지 검사한다
자리나 역할이 다른가	다르면 순열, 같으면 조합이다	두 원소를 뒤집어 같은 결과인지 묻는다
같은 대상을 다시 고르는가	허용 여부에 따라 생성 도구가 달라진다	같은 값 두 개가 든 결과를 검사한다
대상이 칸보다 많은가	그렇다면 같은 칸을 공유한다	버킷별 개수를 확인한다
개수만 필요한가	큰 입력에서는 공식을 우선한다	작은 입력에서 생성 결과와 비교한다

모든 경우를 담지 않고 하나씩 세더라도 생성 시간까지 줄어들지는 않는다. 완성 코드의 생성 검사는 작은 입력을 확인하려는 용도다. 큰 입력의 개수만 필요하다면 공식을 사용하고, 실제 결과도 필요하다면 그 개수를 먼저 계산하여 순회할 수 있는 규모인지 판단한다.

연습 문제

1. 알림 경로가 두 가지이고 메시지 형식이 네 가지다. 모든 경로에서 모든 형식을 지원한다. 가능한 설정을 생성하고 공식과 비교하라. 특정 경로에서 형식 하나를 지원하지 않을 때 개수가 어떻게 바뀌는지도 확인하라.
2. 서로 다른 담당자 네 명 중 두 명을 고른다. 시작 담당자와 검토 담당자를 정하는 경우, 역할 없는 팀을 정하는 경우, 같은 사람이 두 차례 담당해도 되는 순서를 정하는 경우의 개수를 각각 구하라.
3. 옵션 종류가 두 개이고 같은 종류를 여러 번 골라도 된다. 순서를 구별하지 않고 세 개를 고르는 모든 결과를 생성하라. 중복조합 공식과 비교하고, 두 종류를 각각 몇 개 골랐는지로도 설명하라.
4. 키 [2, 6, 10, 3, 7]을 4로 나눈 나머지에 따라 버킷 네 개에 넣어라. 비둘기집 원리로 보장되는 한 버킷의 최소 개수와 실제 가장 큰 버킷의 개수를 구하라. 키가 두 개뿐이어도 충돌하는 부분 입력을 찾아라.

정답과 해설

알림 설정은 여덟 개이며 제한을 반영하면 일곱 개다

각 경로에 형식 네 가지가 붙으므로 2 × 4 = 8이다. 특정 경로와 특정 형식의 짝 하나만 금지되면 그 결과 하나를 제외한다. 제한이 생긴 뒤에도 2 × 4를 그대로 쓰지 않는지 확인한다.

from itertools import product

channels = ["앱", "문자"]
formats = ["요약", "목록", "표", "상세"]
all_cases = list(product(channels, formats))
allowed = [
    case for case in all_cases
    if case != ("문자", "표")
]

assert len(all_cases) == 2 * 4 == 8
assert len(allowed) == 4 + 3 == 7

역할 배치는 열두 개, 팀은 여섯 개, 재선택 순서는 열여섯 개다

서로 다른 두 역할에는 4 × 3가지가 있다. 팀은 각 두 명의 순서를 같은 것으로 취급하므로 그 절반이다. 같은 사람을 다시 골라도 된다면 두 번째 자리에도 네 명이 가능하다.

from itertools import combinations, permutations, product
from math import comb, perm

people = ["가", "나", "다", "라"]

assert len(list(permutations(people, 2))) == perm(4, 2) == 12
assert len(list(combinations(people, 2))) == comb(4, 2) == 6
assert len(list(product(people, repeat=2))) == 4 ** 2 == 16

중복조합은 네 개다

첫 종류의 개수가 0, 1, 2, 3 중 하나면 둘째 종류의 개수는 각각 3, 2, 1, 0으로 정해진다. 점 세 개와 경계 하나의 네 자리에서 점의 위치를 고르는 계산과 같다.

from itertools import combinations_with_replacement
from math import comb

cases = list(combinations_with_replacement(["A", "B"], 3))

assert cases == [
    ("A", "A", "A"),
    ("A", "A", "B"),
    ("A", "B", "B"),
    ("B", "B", "B"),
]
assert len(cases) == comb(2 + 3 - 1, 3) == 4

최소 보장은 두 개이며 실제 최댓값은 세 개다

키 다섯 개를 칸 네 개에 넣으므로 적어도 한 칸에는 두 개가 있다. 실제로 2, 6, 10은 모두 나머지가 2여서 같은 버킷에 들어간다. 비둘기집 원리의 하한은 실제 최댓값과 같을 수도 있고 더 작을 수도 있다. 부분 입력 2와 6만으로도 충돌이 생긴다.

keys = [2, 6, 10, 3, 7]
bucket_count = 4
buckets = [[] for _ in range(bucket_count)]

for key in keys:
    buckets[key % bucket_count].append(key)

lower_bound = (len(keys) + bucket_count - 1) // bucket_count

assert buckets == [[], [], [2, 6, 10], [3, 7]]
assert lower_bound == 2
assert max(len(bucket) for bucket in buckets) == 3
assert 2 % bucket_count == 6 % bucket_count