Генерация номера по объекту и объекта по номеру

Научимся сопоставлять комбинаторному объекту (например, перестановке) его номер в списке всех возможных объектов (списке всех перестановок фиксированной длины), упорядоченном лексикографически; или, наоборот, генерировать объект по его номеру.

Это бывает полезно, если хочется закодировать объект как можно меньшим количеством бит, а также если хочется использовать объект в качестве индекса массива (например, если при применении метода динамического программирования состояние описывается комбинаторным объектом).

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

Как вычислить номер перестановки $p_{1}, \ldots, p_{n}$ чисел $1, \ldots, n$ в списке всех перестановок длины $n$, упорядоченных лексикографически? Например, у нас есть упорядоченный лексикографически список перестановок длины 3:

Номер перестановки $p$ — это количество перестановок, лексикографически меньших $p$. Пусть $q$ — одна из таких перестановок. Тогда $q_{1}=p_{1}, \ldots, q_{k-1}=p_{k-1}, x=q_{k} < p_{k}$ для некоторого $k$. При этом для фиксированных $k, x < p_{k}$ существует ( $n-k$ )! различных перестановок $q$, удовлетворяющих условиям выше (так как оставшиеся $n-k$ чисел могут идти в любом порядке).

Получаем следующий алгоритм: переберём $k$ — позицию самого левого несовпадения $q$ и $p$, переберём $x < p_{k}$ — значение $q_{k}$, и просуммируем количество перестановок $q$ по всем таким $k, x$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

getNum(p, n):
    num = 0
    fill(used, False) # список элементов p[1..k)
    for k = 1..n:
        for x = 1..(p[k] - 1):
            if used[x]:
                continue
            num += factorial[n - k]
        used[p[k]] = True
    return num

Тот же метод (перебрать позицию и значение первого несовпадения, просуммировать по ним количество способов “закончить” объект) работает и со многими другими комбинаторными объектами. Разберём ещё один пример - поиск номера правильной скобочной последовательности.

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

Скобочная последовательность - это любая последовательность символов ‘(’ (открывающая скобка) и ‘)’ (закрывающая скобка).

Балансом скобочной последовательности будем называть разность количества открывающих и закрывающих скобок в ней.

Правильная скобочная последовательность (ПСП) - это такая скобочная последовательность из $2 n$ символов, что баланс любого её префикса неотрицателен, а баланс всей последовательности равен нулю. Например, ниже представлен упорядоченный лексикографически список ПСП длины 8:

Номер по ПСП

Будем искать номер ПСП а длины $2 n$ тем же методом: пусть $b$ лексикографически меньше $a$, причём $b_{1}=a_{1}, \ldots, b_{k-1}=a_{k-1}$; ‘(’ $\left.=b_{k} < a_{k}={ }^{\prime}\right)^{\prime}$. Сколько существует таких ПСП $b$ ?

Поскольку баланс каждого префикса $b$ неотрицателен, баланс каждого суффикса $b$ неположителен. Тогда, если перевернуть суффикс $b_{k+1}, \ldots, b_{2 n}$ и заменить открывающие скобки на закрывающие, а закрывающие - на открывающие, то получится скобочная последовательность длины $2 n-k$, баланс любого префикса которой неотрицателен, а баланс её целиком совпадает с балансом последовательности $b_{1}, \ldots, b_{k}$. Предподсчитаем количество таких последовательностей для каждой длины и каждого значения баланса динамическим программированием (переход - перебор типа последней скобки).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

fill(cnt, 0)
for l = 1..(2 * MAXN):
    for b = 0..l:
        cnt[l, b] = cnt[l - 1, b + 1] # закрывающая скобка
        if b > 0:
            cnt[l, b] += cnt[l - 1, b - 1] # открывающая скобка
getNum(a, n):
    num = 0
    b = 0 # баланс
    for k = 1..(2 * n):
        if a[k] == ')':
            num += cnt[2 * n - k, b + 1]
            b -= 1
        else:
            b += 1
    return num

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

Вернёмся к перестановкам и решим обратную задачу: пусть нужно найти перестановку, имеющую заданный номер num в списке лексикографически упорядоченных перестановок длины $n$.

Для любого $x$ от 1 до $n$ существует ( $n-1$ )! перестановок, начинающихся с $x$. Тогда первый символ искомой перестановки - минимальное $x$ такое, что $x \cdot(n-1)!>n u m$. Остаётся найти перестановку с номером $n u m-x \cdot(n-1)$ ! в списке перестановок, начинающихся с $x$. Для этого будем повторять те же рассуждения, но для следующих символов (второго, третьего, и так далее; надо не забыть, что один символ не может встретиться в перестановке несколько раз).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

getPermutation(num, n):
    fill(used, False)
    vector<int> p
    for k = 1..n:
        for x = 1..n:
            if used[x]:
                continue
            if num < factorial[n - k]:
                p.push_back(x), used[x] = True
                break
            num -= factorial[n - k]
    return p

Тот же метод опять работает и со многими другими комбинаторными объектами. В качестве примера вернёмся к ПСП.

ПСП по номеру

Будем ставить на очередную позицию открывающую скобку, если номер ПСП меньше количества способов закончить ПСП после постановки этой скобки; иначе будем ставить закрывающую скобку и уменьшать номер на количество “пропущенных” ПСП (тех, в которых на этой позиции стоит открывающая скобка).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

getCBS(num, n):
    b = 0
    vector<char> a
    for k = 1..(2 * n):
        if num < cnt[2 * n - k, b + 1]:
            a.push_back('('), b += 1
        else:
            num -= cnt[2 * n - k, b + 1]
            a.push_back(')'), b -= 1
    return a