Алгоритм генерації перестановок

Перестановкою скінченної множини ${\displaystyle \;X}$ називається впорядкований набір без повторів із її елементів.

Всі 6 перестановок 3 кульок

Перестановка — довільна бієкція ${\displaystyle \pi \;:X\to \;X}$. Усього існує ${\displaystyle \;n!}$ (факторіал) різних перестановок, де ${\displaystyle \;n=|X|}$ (потужність множини (кількість елементів у ній)).

Нотація

Для зручності, перестановки розглядають над множиною ${\displaystyle \{1,2,\dots \;,n\}}$ (будь-яку скінченну множину можна однозначно відобразити в цю множину).

У два рядки

Запис ${\displaystyle f={\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\2&5&10&4&3&7&1&9&8&6\end{pmatrix}}}$ означає, що ${\displaystyle f}$ — перестановка множини ${\displaystyle \{1,2,\dots \;,10\}}$ і ${\displaystyle f(1)=2,f(2)=5,\dots \;,f(10)=6}$ (кожне число у верхньому рядку матриці переводиться у відповідне число в нижньому рядку).

В один рядок

Уживанішим у літературі є запис перестановки в один рядок (верхній рядок не пишеться):

${\displaystyle f={\begin{pmatrix}2&5&10&4&3&7&1&9&8&6\end{pmatrix}}}$ (та сама перестановка, що і в прикладі запису у два рядки).

Циклічна

Докладніше: Циклічна перестановка та Циклічний запис (комбінаторика)

Циклом перестановки ${\displaystyle \;\pi }$ називається така послідовність ${\displaystyle \;x_{1},x_{2},\dots \;,x_{n}}$, що ${\displaystyle \pi (x_{1})=x_{2},\pi (x_{2})=x_{3},\dots \;,\pi (x_{n-1})=x_{n},\pi (x_{n})=x_{1}.}$

Приклад:

Перестановка ${\displaystyle f={\begin{pmatrix}1&2&3&4&5&6&7&8&9&10\\2&5&10&4&3&7&1&9&8&6\end{pmatrix}}}$ має три цикли:

1. ${\displaystyle 1\to \;2\to \;5\to \;3\to \;10\to \;6\to \;7\to \;1}$
2. ${\displaystyle 4\to \;4}$
3. ${\displaystyle 8\to \;9\to \;8}$

Циклічний запис перестановки — це запис через її цикли:

${\displaystyle \pi ={\begin{pmatrix}x_{1}^{1}&\dots \;&x_{n_{1}}^{1}\end{pmatrix}}{\begin{pmatrix}x_{1}^{2}&\dots \;&x_{n_{2}}^{2}\end{pmatrix}}\dots \;{\begin{pmatrix}x_{1}^{m}&\dots \;&x_{n_{m}}^{m}\end{pmatrix}}}$

Так для перестановки з прикладу справедливим є запис: ${\displaystyle f={\begin{pmatrix}1&2&5&3&10&6&7\end{pmatrix}}{\begin{pmatrix}4\end{pmatrix}}{\begin{pmatrix}8&9\end{pmatrix}}}$

Пов'язані означення

• Нерухомий елемент перестановки це елемент ${\displaystyle \{x\in X\mid \pi (x)=x\}.}$ Нерухомий елемент є циклом довжини 1.

• Транспозиція — перестановка, що міняє місцями два елементи. Транспозиція є циклом довжини 2.

• Інверсією в перестановці ${\displaystyle \pi }$ називається пара індексів ${\displaystyle i,\ j}$ така, що ${\displaystyle 1\leqslant i<j\leqslant n}$ та ${\displaystyle \pi (i)>\pi (j)}$. Парність числа інверсій в перестановці визначає парність перестановки.

• Безлад — перестановка без нерухомих елементів.

• Декремент перестановки — це кількість елементів мінус кількість циклів. Парність декремента дорівнює парності перестановки.

Група перестановок

Докладніше: Симетрична група

Перестановки скінченної множини ${\displaystyle \;X}$ утворюють групу щодо операції множення перестановок (композиції).

Тотожна перестановка

Нейтральним елементом в групі перестановок є тотожна перестановка ${\displaystyle \;E}$, для якої виконується:

${\displaystyle \forall x\in X:E(x)=x}$

Тотожна перестановка переводить множину${\displaystyle \;X}$ саму в себе.

Добуток перестановок

Композиція перестановок

Добуток перестановок — це послідовне виконання двох перестановок (композиція).

Якщо ${\displaystyle \;f,g}$ — перестановки, то:

${\displaystyle c=f\times \;g\Leftrightarrow \;\forall \;x\in \;X:c(x)=g(f(x))}$.

Наприклад, нехай маємо ${\displaystyle A={\begin{pmatrix}a&b&c&d&e&f\\c&d&a&f&b&e\end{pmatrix}},\quad \quad B={\begin{pmatrix}a&b&c&d&e&f\\f&e&d&c&b&a\end{pmatrix}}.}$

Переставимо стовпці у ${\displaystyle B}$, щоб її верхній ряд збігався із нижнім рядом ${\displaystyle A.}$

${\displaystyle A\circ B={\begin{pmatrix}a&b&c&d&e&f\\c&d&a&f&b&e\end{pmatrix}}\circ {\begin{pmatrix}c&d&a&f&b&e\\d&c&f&a&e&b\end{pmatrix}}={\begin{pmatrix}a&b&c&d&e&f\\d&c&f&a&e&b\end{pmatrix}}.}$.

Обернений елемент

Кожна перестановка має обернену перестановку.

${\displaystyle \forall }$ перестановки ${\displaystyle f,\;\exists \;f^{-1}}$ така що:

${\displaystyle f\times \;f^{-1}=f^{-1}\times \;f=E}$

Алгоритми на перестановках

Алгоритм отримання всіх перестановок

Наведений нижче алгоритм дозволяє послідовно отримати всі перестановки скінченної множини. Для зручності будемо вважати, що елементами множини є числа від 1 до n, що записані у масив A.

1. Спочатку ${\displaystyle \forall i:A[i]=i}$ (В масиві записана тотожна перестановка)
2. Проглядаючи елементи з кінця масиву, знаходимо найбільше ${\displaystyle \;i}$ таке, що ${\displaystyle \;A[i]<A[i+1]}$.
   Якщо такого не має, то завершуємо роботу.
3. Знаходимо максимальне ${\displaystyle \;j,j>i}$ таке, що ${\displaystyle \;A[j]>A[i]}$
4. Міняємо місцями ${\displaystyle \;i}$-й і ${\displaystyle \;j}$-й елементи: ${\displaystyle A[i]\leftrightarrow A[j]}$
5. Перегортаємо частину масиву з ${\displaystyle \;i+1}$-го по останній (${\displaystyle \;n}$-й) індекси включно:

   ${\displaystyle \forall k={\overline {i+1,\lfloor (i+n+1)/2\rfloor }}:A[k]\leftrightarrow A[i+n+1-k]}$

6. Отримана нова перестановка. Повертаємося до п. 2.

Аналіз складності алгоритму

Кількість елементів, що розглядаються чи опрацьовуються на кроках 3 і 5 не перевищує кількість елементів, що переглядаються на кроці 2. На кроці 4 завжди виконується тільки одна операція обміну елементів. Отже, визначальною для складності алгоритму є кількість операцій на кроці 2. Вона залежить від поточного стану множини і може змінюватися від 1 до n − 1. Для визначення складності алгоритму достатньо оцінити середню кількість операцій на кроці 2.

Кількість перестановок для яких на кроці 2 буде переглядатись рівно ${\displaystyle \;k}$ елементів така — ${\displaystyle C_{n}^{k+1}\cdot C_{k+1}^{2}\cdot (n-k-1)!}$.

Середня кількість переглядів елементів на кроці 2 для всіх можливих перестановок: ${\displaystyle {\frac {1}{n!}}\sum _{k=1}^{n-1}k\cdot C_{n}^{k+1}\cdot C_{k+1}^{2}\cdot (n-k-1)!=}$

${\displaystyle ={\frac {1}{n!}}\sum _{k=1}^{n-1}k\cdot {\frac {n!}{(k+1)!(n-k-1)!}}\cdot {\frac {(k+1)!}{2\cdot (k-1)!}}\cdot (n-k-1)!={\frac {1}{2}}\sum _{k=0}^{n-2}{\frac {k+1}{k!}}<{\frac {1}{2}}\sum _{k=0}^{\infty }{\frac {k+1}{k!}}=e<3}$

Отже, в середньому на кроці 2 виконується менше ніж три перегляди елементів. Значить, такого ж порядку кількість операцій виконується на кроках 3 і 5. Звідси випливає, що отримання нової перестановки відбувається в середньому за константну кількість операцій ${\displaystyle \;O(1)}$, тоді складність алгоритму отримання всіх перестановок буде відповідно ${\displaystyle \;O(n!)}$.

Приклад роботи

Для прикладу отримаємо всі перестановки множини з трьох елементів, розглянемо стани масиву на початку п. 2, а також відповідні індекси ${\displaystyle \;i,j}$:

1. A = (1, 2, 3) (i = 2, j = 3)
2. A = (1, 3, 2) (i = 1, j = 3)
3. A = (2, 1, 3) (i = 2, j = 3)
4. A = (2, 3, 1) (i = 1, j = 2)
5. A = (3, 1, 2) (i = 2, j = 3)
6. A = (3, 2, 1) — завершення алгоритму.

Алгоритм послідовно отримав всі 6 можливих перестановок.

Алгоритм отримання кореня з перестановки

Коренем з перестановки ${\displaystyle \;\pi }$ називається така перестановка ${\displaystyle \;\psi }$, що ${\displaystyle \;\psi ^{2}=\pi }$.

Справедливе наступне твердження: ${\displaystyle \forall \pi }$ — перестановка ${\displaystyle \exists k\in N:\pi ^{k}=E}$. Звідси випливає, що ${\displaystyle \;\pi ^{k+1}=\pi }$. Якщо ${\displaystyle k+1\;}$ парне, то ${\displaystyle \pi ^{\frac {k+1}{2}}=\psi }$ — корінь із перестановки.

${\displaystyle \;k=HCK(n_{1},n_{2},...,n_{l})}$, де НСК — найменше спільне кратне, а ${\displaystyle \;n_{i}}$ — довжина i-го циклу в циклічному записі перестановки ${\displaystyle \;\pi }$. Отже, якщо всі ${\displaystyle \;n_{i}}$ непарні, то k — непарне, а k+1 — парне, і корінь з перестановки гарантовано існує (достатньо просто піднести початкову перестановку до відповідного степеня).

Цей розв'язок неприйнятний, якщо перестановка має цикли парної довжини. Але це не означає, що таки перестановки взагалі не мають коренів.

Теорема про існування кореня з перестановки

Корінь з перестановки існує тоді і тільки тоді, якщо ${\displaystyle \forall k\in N}$ кількість циклів перестановки довжини ${\displaystyle \;2k}$ — парна.

Доведення

Спочатку доведемо необхідність умови. Припустимо існує корінь ${\displaystyle \;\psi ,\psi ^{2}=\pi }$. Розглянемо циклічне представлення цієї перестановки: ${\displaystyle \;\psi =(x_{1}^{1},...,x_{l_{1}}^{1})...(x_{1}^{m},...,x_{l_{m}}^{m})}$.

Якщо i-й цикл ${\displaystyle (x_{1},...,x_{l_{i}})\;}$ має непарну довжину, то при піднесенні перестановки до квадрата, він перейде в цикл ${\displaystyle (x_{1},x_{3},...,x_{2t+1},...,x_{l_{i}},x_{2},x_{4},...,x_{2p},...,x_{l_{i}-1})\;}$ — теж непарної довжини. Тобто якщо в перестановці якийсь елемент належав циклові непарної довжини, то і у квадраті цієї перестановки елемент буде належати циклові непарної довжини.

Якщо ж i-й цикл ${\displaystyle (x_{1},...,x_{l_{i}})\;}$ має парну довжину, то при піднесенні перестановки до квадрата, він перейде у два цикли однакової довжини ${\displaystyle (x_{1},x_{3},...,x_{2t+1},...,x_{l_{i}-1})\;}$ і ${\displaystyle (x_{2},x_{4},...,x_{2p},...,x_{l_{i}})\;}$.

Цикли парної довжини у квадраті перестановки могли утворитись тільки з циклів парної довжини. А отже, якщо є один цикл парної довжини, то обов'язково існує і інший такої самої довжини.

Доведення достатності випливає з алгоритму знаходження кореня.

Опис алгоритму

1. Представити перестановку в циклічному вигляді.
2. Перевірити виконання умови теореми. Якщо не виконується, то корінь не існує — завершити роботу.
3. Перетворити кожен цикл непарної довжини ${\displaystyle (x_{1},\dots ,x_{l})\;}$ на цикл ${\displaystyle (x_{1},x_{{\frac {l+1}{2}}+1},x_{2},x_{{\frac {l+1}{2}}+2},\dots ,x_{k},x_{{\frac {l+1}{2}}+k},\dots ,x_{{\frac {l+1}{2}}-1},x_{l},x_{\frac {l+1}{2}})\;}$
4. Розділити цикли парної довжини на пари рівної довжини. Кожну пару циклів ${\displaystyle (x_{1}^{1},...,x_{l}^{1})\;}$ і ${\displaystyle (x_{1}^{2},...,x_{l}^{2})\;}$ об'єднати в один цикл

   ${\displaystyle (x_{1}^{1},x_{1}^{2},x_{2}^{1},x_{2}^{2},\dots ,x_{k}^{1},x_{k}^{2},\dots ,x_{l}^{1},x_{l}^{2})\;}$

Оцінка складності

Кожен із 4 кроків алгоритму може бути виконаний за час ${\displaystyle O(n)\;}$, отже загальна складність — ${\displaystyle O(n)\;}$.

Приклад використання

Для прикладу знайдемо корінь з перестановки ${\displaystyle \;\pi ={\begin{pmatrix}1&2&3&4&5&6&7\\3&4&1&7&6&5&2\end{pmatrix}}}$

1. Циклічне представлення ${\displaystyle \;\pi ={\begin{pmatrix}2&4&7\end{pmatrix}}{\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}5&6\end{pmatrix}}}$
2. Циклів довжини два, парна кількість, умова теореми виконується.
3. Перетворимо цикл непарної довжини ${\displaystyle {\begin{pmatrix}2&4&7\end{pmatrix}}\to {\begin{pmatrix}2&7&4\end{pmatrix}}}$
4. Перетворимо пару циклів парної довжини ${\displaystyle {\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}5&6\end{pmatrix}}\to {\begin{pmatrix}1&5&3&6\end{pmatrix}}}$

Шукана перестановка виглядає так: ${\displaystyle \psi ={\begin{pmatrix}1&2&3&4&5&6&7\\5&7&6&2&3&1&4\end{pmatrix}}}$, легко переконатись, що ${\displaystyle \psi ^{2}=\pi \;}$.

Зауваження

Наведений алгоритм знаходить тільки один корінь, в загальному ж випадку коренів може бути декілька.

Перестановки з повторенням

Розглянемо n елементів m різних типів, причому в кожному типі всі елементи однакові. Тоді перестановки із всіх цих елементів з точністю до порядку розміщення однотипних елементів називаються перестановками з повторенням. Якщо k_i — кількість елементів i-го типу, то ${\displaystyle k_{1}+k_{2}+\dots +k_{m}=n}$ і кількість можливих перестановок з повтореннями дорівнює мультиноміальному коефіцієнту ${\displaystyle \textstyle {\binom {n}{k_{1},\ k_{2},\ \dots ,\ k_{m}}}={\frac {n!}{k_{1}!k_{2}!\dots k_{m}!}}.}$

Див. також

• Псевдовипадкова перестановка
• Підстановка
• Алгоритм сортування
• Розміщення

Джерела

• В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 2010. — 324 с. — .(укр.)
• ^[en]. An Introduction to the Theory of Groups. — 4th. — Springer (Graduate Texts in Mathematics), 1994. — 532 с. — .(англ.)
• Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.)