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

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

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

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

Как вычислить номер перестановки $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
11
12
13
14
15

def perm_to_num(p: list[int], factorial: list[int]) -> int:
    """
    p — перестановка чисел 1..n (0-индексированная: p[0]..p[n-1]).
    factorial[k] = k!
    Возвращает лексикографический номер перестановки.
    """
    n = len(p)
    used = [False] * (n + 1)
    num = 0
    for k in range(n):
        for x in range(1, p[k]):
            if not used[x]:
                num += factorial[n - 1 - k]
        used[p[k]] = True
    return num

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

#include <vector>
using namespace std;

// p — перестановка 1..n, factorial[k] = k!
long long permToNum(vector<int>& p, vector<long long>& factorial) {
    int n = p.size();
    vector<bool> used(n + 1, false);
    long long num = 0;
    for (int k = 0; k < n; k++) {
        for (int x = 1; x < p[k]; x++)
            if (!used[x])
                num += factorial[n - 1 - k];
        used[p[k]] = true;
    }
    return num;
}

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

Ниже представлен лексикографически упорядоченный список ПСП длины 8:

Номер по ПСП

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def build_cnt(maxn: int) -> list[list[int]]:
    """
    cnt[l][b] = число скобочных последовательностей длины l и баланса b,
    у которых все префиксы имеют неотрицательный баланс.
    """
    cnt = [[0] * (maxn + 1) for _ in range(2 * maxn + 1)]
    cnt[0][0] = 1
    for l in range(1, 2 * maxn + 1):
        for b in range(l + 1):
            cnt[l][b] = cnt[l-1][b+1] if b + 1 <= l else 0  # ')'
            if b > 0:
                cnt[l][b] += cnt[l-1][b-1]                  # '('
    return cnt

def psp_to_num(a: str, cnt: list[list[int]]) -> int:
    """Возвращает лексикографический номер ПСП a."""
    n = len(a) // 2
    num = 0
    balance = 0
    for k, ch in enumerate(a):
        remaining = len(a) - k - 1
        if ch == ')':
            num += cnt[remaining][balance + 1]
            balance -= 1
        else:
            balance += 1
    return num

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <vector>
using namespace std;

// cnt[l][b] = число допустимых скобочных последовательностей длины l и баланса b
vector<vector<long long>> buildCnt(int maxN) {
    int sz = 2 * maxN + 1;
    vector<vector<long long>> cnt(sz, vector<long long>(sz + 1, 0));
    cnt[0][0] = 1;
    for (int l = 1; l < sz; l++)
        for (int b = 0; b <= l; b++) {
            if (b + 1 <= l) cnt[l][b] += cnt[l-1][b+1];  // ')'
            if (b > 0)      cnt[l][b] += cnt[l-1][b-1];   // '('
        }
    return cnt;
}

long long pspToNum(const string& a, vector<vector<long long>>& cnt) {
    int m = a.size();
    long long num = 0;
    int balance = 0;
    for (int k = 0; k < m; k++) {
        int remaining = m - k - 1;
        if (a[k] == ')') {
            num += cnt[remaining][balance + 1];
            balance--;
        } else {
            balance++;
        }
    }
    return num;
}

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

Вернёмся к перестановкам и решим обратную задачу: найти перестановку с заданным номером num.

Для любого $x$ от 1 до $n$ существует $(n-1)!$ перестановок, начинающихся с $x$. Тогда первый символ искомой перестановки — минимальное $x$ такое, что накопленное число не превышает num. Далее повторяем те же рассуждения для следующих позиций.

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

def num_to_perm(num: int, n: int, factorial: list[int]) -> list[int]:
    """Возвращает перестановку 1..n с лексикографическим номером num."""
    used = [False] * (n + 1)
    p = []
    for k in range(n):
        for x in range(1, n + 1):
            if used[x]:
                continue
            if num < factorial[n - 1 - k]:
                p.append(x)
                used[x] = True
                break
            num -= factorial[n - 1 - k]
    return p

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

vector<int> numToPerm(long long num, int n, vector<long long>& factorial) {
    vector<bool> used(n + 1, false);
    vector<int> p;
    for (int k = 0; k < n; k++) {
        for (int x = 1; x <= n; x++) {
            if (used[x]) continue;
            if (num < factorial[n - 1 - k]) {
                p.push_back(x);
                used[x] = true;
                break;
            }
            num -= factorial[n - 1 - k];
        }
    }
    return p;
}

ПСП по номеру

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

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

def num_to_psp(num: int, n: int,
               cnt: list[list[int]]) -> str:
    """Возвращает ПСП длины 2n с лексикографическим номером num."""
    result = []
    balance = 0
    for k in range(2 * n):
        remaining = 2 * n - k - 1
        # сколько ПСП начинается с '(' на этой позиции?
        ways_open = cnt[remaining][balance + 1] if balance + 1 <= remaining else 0
        if num < ways_open:
            result.append('(')
            balance += 1
        else:
            num -= ways_open
            result.append(')')
            balance -= 1
    return ''.join(result)

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

string numToPSP(long long num, int n,
                vector<vector<long long>>& cnt) {
    string result;
    int balance = 0;
    for (int k = 0; k < 2 * n; k++) {
        int remaining = 2 * n - k - 1;
        long long waysOpen = (balance + 1 <= remaining)
                             ? cnt[remaining][balance + 1] : 0;
        if (num < waysOpen) {
            result += '(';
            balance++;
        } else {
            num -= waysOpen;
            result += ')';
            balance--;
        }
    }
    return result;
}