Таблица перестановок¶

Таблица перестановок — это структура данных или математическая модель, используемая для представления, хранения и анализа перестановок (комбинаторных объектов, описывающих упорядочивание элементов конечного множества). В зависимости от контекста термин может обозначать матрицу, список, графическую схему или алгоритмическую конструкцию, фиксирующую взаимно однозначное отображение множества на себя.

¶Определение и основные понятия

Перестановкой конечного множества из \(n\) элементов называется биективное отображение \(\sigma\) этого множества на себя. В комбинаторике перестановки обычно записывают в виде таблицы из двух строк: в верхней строке указывают исходные позиции (или элементы), а в нижней — соответствующие им образы после перестановки. Такую запись называют двустрочной таблицей перестановки:

\[ \sigma = \begin{pmatrix} 1 & 2 & 3 & \dots & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \dots & \sigma(n) \end{pmatrix} \]

Здесь \(\sigma(i)\) — элемент, на который отображается \(i\)-й элемент исходного множества. Например, для множества \(\{1,2,3\}\) перестановка, меняющая местами первый и второй элементы, записывается как:

\[ \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} \]

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

¶Виды таблиц перестановок

¶Матрица перестановки

В линейной алгебре матрица перестановки — это квадратная бинарная матрица размера \(n \times n\), в каждой строке и каждом столбце которой ровно одна единица, а остальные элементы — нули. Такая матрица кодирует перестановку: если \(\sigma(i) = j\), то в \(i\)-й строке и \(j\)-м столбце ставится единица. Умножение вектора на матрицу перестановки переставляет его координаты в соответствии с заданной перестановкой.

Матрицы перестановок являются ортогональными: их определитель равен \(\pm 1\), а обратная матрица совпадает с транспонированной. Они широко применяются в численных методах (например, при LU-разложении для выбора главного элемента) и в теории групп.

¶Таблица инверсий

Таблица инверсий (или вектор инверсий) — это последовательность \(d_1, d_2, \dots, d_n\), где \(d_i\) — количество элементов, расположенных левее \(i\)-го элемента в перестановке и имеющих большее значение. Таблица инверсий однозначно определяет перестановку и используется для её кодирования, а также в алгоритмах сортировки и генерации перестановок. Например, для перестановки \((3,1,2)\) таблица инверсий будет \((2,0,0)\).

¶Таблица Кэли

В теории групп таблица Кэли (или таблица умножения) конечной группы — это квадратная таблица, строки и столбцы которой соответствуют элементам группы, а на пересечении строки \(a\) и столбца \(b\) записывается результат групповой операции \(a \circ b\). Для группы перестановок (симметрической группы \(S_n\)) таблица Кэли показывает результат композиции двух перестановок. Такая таблица позволяет изучать структуру группы, но для больших \(n\) становится громоздкой.

¶Таблица перестановок в комбинаторных алгоритмах

В программировании под таблицей перестановок часто понимают массив или список, хранящий последовательность индексов или значений, задающих порядок элементов. Например, в алгоритмах сортировки (таких как сортировка перестановкой) таблица перестановок используется для записи порядка следования элементов после сортировки. В криптографии таблицы перестановок применяются в блочных шифрах (например, в алгоритме DES — Data Encryption Standard, разработанном в США в 1970-х годах) для перемешивания битов данных.

¶Применение таблиц перестановок

¶Комбинаторика и дискретная математика

Таблицы перестановок являются основным инструментом для изучения свойств перестановок: чётности, цикловой структуры, порядка. С их помощью формулируются комбинаторные тождества, доказываются теоремы (например, теорема Кэли о представлении конечных групп подстановками). В комбинаторной оптимизации таблицы перестановок используются для кодирования решений в задачах о назначениях, коммивояжёра и других.

¶Криптография

В симметричных шифрах таблицы перестановок (P-блоки) выполняют функцию перемешивания битов, что повышает стойкость шифра к линейному и дифференциальному криптоанализу. Например, в стандарте шифрования ГОСТ 28147-89 (Россия, 1989 год) используется фиксированная таблица перестановок для начальной и конечной перестановки битов. В современных алгоритмах (AES, «Кузнечик» — стандарт ГОСТ Р 34.12-2015) перестановки задаются в виде матриц или таблиц замен.

¶Теория кодирования

В помехоустойчивом кодировании таблицы перестановок применяются для построения перемежителей (interleavers) — устройств, изменяющих порядок символов кодового слова для борьбы с пакетными ошибками. Такие таблицы задают закон перемежения и могут быть как фиксированными, так и адаптивными.

¶Машинное обучение и обработка данных

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

¶Примеры

¶Пример 1: Двустрочная запись

Для перестановки \(\sigma\) на множестве \(\{1,2,3,4\}\), где \(\sigma(1)=3, \sigma(2)=1, \sigma(3)=4, \sigma(4)=2\), двустрочная таблица имеет вид: \[ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix} \]

¶Пример 2: Матрица перестановки

Для той же перестановки матрица перестановки \(P\) размера \(4 \times 4\): \[ P = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} \]

¶Пример 3: Таблица инверсий

Для перестановки \((4,2,1,3)\) таблица инверсий: \(d_1=3\) (элемент 4 больше трёх элементов слева), \(d_2=1\) (элемент 2 больше элемента 1), \(d_3=0\), \(d_4=0\). Итог: \((3,1,0,0)\).

¶Критика и ограничения

Таблицы перестановок в виде двустрочной записи или матрицы становятся неэффективными при больших \(n\) (например, \(n > 10^6\)) из-за квадратичного роста объёма данных. В таких случаях предпочтительнее использовать компактные представления: цикловую запись, таблицу инверсий или специализированные структуры данных (например, деревья Фенвика для быстрого вычисления инверсий). Кроме того, в криптографии фиксированные таблицы перестановок могут быть уязвимы для атак, если они не обладают достаточной нелинейностью.

¶Интересные факты

• Таблицы перестановок используются в теории игр для анализа стратегий: например, в игре «Судоку» каждая строка, столбец и блок являются перестановками чисел от 1 до 9.
• В русской математической школе таблицы перестановок часто называют «подстановками», а двустрочную запись — «записью подстановки в виде двух строк».
• В 2023 году в России был утверждён новый стандарт криптографической защиты «Кузнечик» (ГОСТ Р 34.12-2015), в котором таблицы перестановок задаются в виде S-блоков (таблиц замен) и P-блоков (таблиц перестановок битов).

¶Источники

• Виленкин Н. Я. Комбинаторика. — М.: Наука, 1969.
• Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра: Учебник. — М.: Гелиос АРВ, 2003.
• Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск. — М.: Вильямс, 2007.
• Шнайер Б. Прикладная криптография. — М.: Триумф, 2002.
• ГОСТ Р 34.12-2015. Информационная технология. Криптографическая защита информации. Блочные шифры.