Алгоритмы генерации и нумерации комбинаторных объектов

Двоичные вектора фиксированной длины

Пример:

gen:
    gen all, starting with 0
    gen all, starting with 1

Рекурсивный вызов:

gen(p):
    if len(p)=n:
        print p
        return
    gen(p+[0])
    gen(p+[1])

main:
    gen([])

Перестановки

gen(p):
    if len(p) = n
        print(p)
        return
    for i = 1..n:
        if i not in p:
            gen(p+[i])
            
main:
    gen([])

Все строки из и длины

gen(p):
    print(p)
    if len(p) = n:
        return
    gen(p + [0])
    gen(p + [1])

Общая запись

- префикс комбинаторного объекта

gen(p):
    if (p = комбинаторный объект):
        print(p)
    for (C in ∑): (перебор в возрастающем порядке):
        if (p + [C] - префикс комбинаторного объекта):
            gen(p+[C])

Сочетания

gen(p):
    if len(p) = k:
        print(p)
        return
    for (c = 1 .. n):
        if p ≠ [] and C ≤ p[-1]:
            continue
        if n - c < k - len(p) - 1:
            continue
        gen(p+[c])

Правильные скобочные последовательности

Баланс
В конце баланс равен

gen(p):
    if len(p) = 2n:
        print(p)
        return
    if bal + 1 ≤ 2n-len(p)-1;
        gen(p+["("], bal+1)
    if bal > 0:
        gen(p+[")"], bal-1)

main:
    gen([], 0)

Оптимизируем (Перестановки)

a = <...>
used = <...> - взятые элементы
gen(p): p - длина префикса
    if p == n:
        print(a)
        return
    for i = 1 .. n:
        if !used[i]
            used[i] = true
            a[p] = i
            gen(p+1)
            used[i] = false

Нумеруем перестановки

gen(p):
    if p == n:
        if k == 0:
            print(a)
        k--
        return
    for i = 1 .. n:
        if !used[i]:
            if k ≥ (n-p-1)!:
                k -= (n-p-1)!
            else:
                used[i] = true
                a[p] = i
                gen(p+1)
                return

Нумеруем в общем случае

gen(p):
    if (p = комбинаторный объект):
        print(p)
    for (C in ∑): (перебор в возрастающем порядке):
        if (p + [C] - префикс комбинаторного объекта):
            t = кол-во комбинаторных объектов с префиксом p+[c]
            if k ≥ t:
                k -= t
            else gen(p+[c]):
                return

Если фиксированно (например ), то мы можем заранее посчитать сколько пропусков нужно сделать
Тогда берём й неиспользованный элемент перестановка по номеру за

Сочетания по номеру

gen(p):
    if p == m:
        print(a)
        return
    for p == 0 ? 0 : a[p-1] ... n - m + p + 1
        t = C(n-c, m-p-1)
        if k ≥ t:
            k -= t
        else:
            gen(p+1)

- к.о.

gen(p):
    if p-комбианторный объект:
        if p == z:
            res = k
        else:
            k++
    for (c in ∑):
        if (p + [c] префикс ко):
            gen(p+[c])

Общий универсальный алгоритм для следующего к.о. (Next permutation)

1. - максимальный префикс, который можно сохранить увеличив следующий
2. Следующий элемент нужно увеличить минимальным образом
3. - элементу нужно приписать минимальный "хвост"

Пример (Двоичный вектор):
Пример (Перестановка):