Разбиения числа и множества: перечислить без повторов и сосчитать

Если ты умеешь перечислять разбиения числа по невозрастанию, считать их динамикой размена и отличаешь их от разбиений множества, листай до «Теперь сам».

Как думаешь, сколько способов разложить шесть

Шесть одинаковых задач раздать по исполнителям так, чтобы у каждого было хотя бы по одной, - сколько существенно разных раскладок, если исполнители не различаются (важно только, сколько у кого)?

Прежде чем читать дальше, попробуй выписать их руками. Наверняка в списке окажутся 2 + 4 и 4 + 2 - и тут же вопрос: это одно и то же или нет? А если задачи РАЗНЫЕ - «отчёт», «звонок», «письмо», - сколько способов разбить их на группы?

На что это похоже

Сдача мелочи без учёта порядка монет. 5 + 1 + 1 и 1 + 5 + 1 - одна и та же горсть. Кассир, который хочет перечислить все горсти без повторов, выкладывает монеты от крупной к мелкой: следующая монета не крупнее предыдущей. Тогда каждая горсть получается ровно один раз - в своём единственном «отсортированном» виде.

Разбиение множества похоже на рассадку разных гостей по столам, где столы не подписаны. Важно, кто с кем сидит, а не за каким столом. Чтобы не считать одну рассадку дважды, столы нумеруют по порядку появления: первый гость всегда за столом 0, каждый следующий - за одним из занятых или за новым следующим по номеру.

Механизм: невозрастание, размен и номера групп

ПЕРЕЧИСЛЕНИЕ РАЗБИЕНИЙ ЧИСЛА
разбить(n, макс): для части от min(n, макс) до 1:
    записать часть, разбить(n − часть, часть)
порядок частей - невозрастающий, и каждое разбиение ровно одно

ПОДСЧЁТ БЕЗ ПЕРЕЧИСЛЕНИЯ - как размен монет
p[0] = 1; для каждой «монеты» k = 1..n:
    для m = k..n:  p[m] += p[m − k]
внешний цикл по монетам - и порядок частей не важен; Θ(n²)

РАЗБИЕНИЯ МНОЖЕСТВА {0, …, n−1}
элемент i получает номер группы g ≤ (наибольший номер у 0..i−1) + 1
первый всегда в группе 0; число таких записей - число Белла B(n)

Почему внешний цикл по монетам убирает порядок. Обходя монеты по одной, мы сначала строим все суммы только из единиц, потом добавляем двойки, потом тройки - каждое разбиение собирается в одном порядке: «сначала все единицы, потом все двойки, …». Если поставить циклы наоборот (сумма снаружи, монеты внутри), каждая перестановка слагаемых посчитается отдельно - это уже число упорядоченных сумм.

Правило

Разбиения числа перечисляют без повторов, ставя части по невозрастанию: рекурсия передаёт наибольшую разрешённую часть. Считают их динамикой размена с внешним циклом по частям - Θ(n²). Разбиения МНОЖЕСТВА различных элементов перечисляют, давая элементу номер группы не больше «текущий максимум + 1»; их число - число Белла. Растут обе величины сверхполиномиально, и перечисление годится только для малых n.

Разбор: разбиения пяти

разбить(5, 5): части 5, 4, 3, 2, 1
  5
  4 + разбить(1, 4) → 4 + 1
  3 + разбить(2, 3) → 3 + 2,  3 + 1 + 1
  2 + разбить(3, 2) → 2 + 2 + 1,  2 + 1 + 1 + 1
  1 + разбить(4, 1) → 1 + 1 + 1 + 1 + 1
итого 7

подсчёт размена: p после монеты 1: [1 1 1 1 1 1]
                 после 2:          [1 1 2 2 3 3]
                 после 3:          [1 1 2 3 4 5]
                 после 4:          [1 1 2 3 5 6]
                 после 5:          [1 1 2 3 5 7]    p(5) = 7

В ветке «2 + …» нельзя взять 3: это дало бы 2 + 3, а оно уже есть как 3 + 2. Ограничение «не больше предыдущей части» и есть защита от повторов.

Разбор: от шести до ста и от разбиения числа к разбиению множества

Программа перечисляет разбиения шести, считает p(n) до ста разменом и сверяет со счётом перечислением до тридцати, затем считает числа Белла треугольником и сверяет их с перебором номеров групп до восьми.

def razbieniya(n, maks=None, nachalo=()):   # части не возрастают
    if maks is None:
        maks = n
    if n == 0:
        yield nachalo
        return
    for chast in range(min(n, maks), 0, -1):
        yield from razbieniya(n - chast, chast, nachalo + (chast,))


def schitat(n):                       # p[m]: части 1..k, как размен
    p = [1] + [0] * n
    for chast in range(1, n + 1):
        for m in range(chast, n + 1):
            p[m] += p[m - chast]
    return p


def mnozhestva(n):                    # разбиения МНОЖЕСТВА: числа Белла
    stroka, bell = [1], [1]
    for _ in range(n):                # треугольник Белла
        nov = [stroka[-1]]
        for x in stroka:
            nov.append(nov[-1] + x)
        stroka = nov
        bell.append(stroka[0])
    return bell


def gruppy(n, nomera=()):            # номер группы каждого элемента:
    if len(nomera) == n:              # новый номер - не больше max + 1
        yield nomera
        return
    for g in range(max(nomera, default=-1) + 2):
        yield from gruppy(n, nomera + (g,))


for r in razbieniya(6):
    print(" + ".join(map(str, r)))
p = schitat(100)
for n in range(31):
    assert p[n] == sum(1 for _ in razbieniya(n))
print("p(10) =", p[10], " p(30) =", p[30], " p(100) =", p[100])
b = mnozhestva(30)
for n in range(9):
    assert b[n] == sum(1 for _ in gruppy(n))
print("разбиений множества: B(10) =", b[10], " B(30) =", b[30])

6
5 + 1
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1
p(10) = 42  p(30) = 5604  p(100) = 190569292
разбиений множества: B(10) = 115975  B(30) = 846749014511809332450147

У шести одиннадцать разбиений. p(100) - почти двести миллионов: перечислять их ещё можно, но медленно; p(1000) - тридцать два знака, и остаётся только считать. Разбиений множества из тридцати элементов - 8.5 · 10²³, примерно в 10²⁰ раз больше, чем разбиений числа тридцать: различимость предметов умножает варианты.

Что ломается без этого

Первая ошибка - перечислять без ограничения «не больше предыдущей части»: каждое разбиение появится столько раз, сколько у него различных перестановок, и счёт уйдёт к упорядоченным суммам (их у n ровно 2^(n−1)). Вторая - в подсчёте поменять циклы местами: получится число упорядоченных сумм, а не разбиений. Третья - путать разбиение числа (одинаковые предметы) с разбиением множества (различные): задача «разделить 10 разных задач между неразличимыми командами» - это Белл, 115 975 вариантов, а не 42. Четвёртая - пытаться перебрать разбиения при n в сотни: их число растёт как e^(c·√n), и перебор кончается задолго до ста.

Зачем это в работе

Разбиения числа появляются, когда делят одинаковые ресурсы: как разложить объём на партии, сколько способов набрать сумму купюрами, перебор конфигураций однотипных серверов. Разбиения множества - кластеризация: перебор всех способов разбить небольшой набор объектов на группы, разбиение задач между командами, проверка алгоритмов кластеризации на маленьких входах точным перебором. И везде первым делом стоит спросить: предметы одинаковые или разные, порядок важен или нет - это четыре разные задачи с разными ответами.

Теперь сам

Выпиши все разбиения числа 5 на части, каждая из которых не больше 2. Сколько их? Сверь с таблицей размена, остановленной после «монеты» 2.