AlgorithmO #7 - Декодиране на пермутации (получаване на пермутация от номера й в лексикографски ред)

Днес ще продължа по темата за комбинаторни алгоритми и по-конкретно за алгоритмите, които са свързани с пермутации.

В предишния си пост ви показах как да кодираме пермутации като цели числа според номерa им в лексикографски ред.

Днес ще ви покажа обратното - как, от номер на пермутация от N елемента, да получим самата пермутация. По-лесно е отколкото може би предполагате...

---

Source: http://retrazos.pe/droppop-en/permutations

ОПИСАНИЕ:

Този алгоритъм "декодира" дадена пермутация ако знаем нейния код (номера й в лексикографски ред) и броя на елементите й.

АЛГОРИТЪМ:

1. Определяме броя на елементите на пермутацията (даден по условие, N елемента)

2. Разбиваме кода на пермутацията на сума от произведения (спомнете си формулата от миналия пост):

Код на пермутация = _ * (N-1)! + _ * (N-2)! + ... _ * 1!

... където '_' е празно място за броя елементи, които са по-малки и стоящи надясно от елемента, стоящ на позиция 'i' в пермутацията, която търсим, като 'i' е от 1 до N включително.

3. Делим целочислено кода на пермутацията на (N-1)!

4. Остатъкът от делението делим на (N-2)! и продължаваме да делим със следващия остатък докато не стигнем делител 1! и получим резултата от това деление

5. Заместваме последователно празните места в горната формула с частното от всяко целочислено деление (НЕ с остатъка). Резултатът от първото деление ще е числото, което ще заместим на първото място във формулата и аналогично със следващите.

6. Създаваме множество S, което съдържа всички елементи от 1 до N.

7. Създаваме празно множество P.

8. Докато елементите на P не станат N на брой:

- Вземаме елемент от S

- Ако числото на 'i'-тото запълнено празно място в горната формула е равно на броя елементи в S, които са по-малки от избрания от нас елемент, добавяме този елемент към P и увеличаваме 'i' с 1 (следващия път ще сравняваме с числото на следващото запълнено празно място)

- Иначе избираме друг елемент от S и повтаряме

Накрая P ще съдържа пермутацията, която търсим.

ПРИМЕР:

Нека имаме следния код (или номер) на пермутация:

567 (6 елемента)

По условие виждаме, че N = 6.

Това значи, че формулата ни ще изглежда така:

567 = (_ * 5!) + (_ * 4!) + (_ * 3!) + (_ * 2!)  + (_ * 1!)

Нашата цел сега е да запълним горните празни места.

Започваме да делим номера на пермутацията на 5! (т.е. на (N-1)!):

567 : (5!) = 567 : 120 = 4  

=> (4 * 120 = 480, остатък 87)

В случая ни интересуват две числа - частното от делението (4) и остатъкът (87). Частното поставяме в горната формула на първото празно място, а с остатъкът ще продължим да делим по-нататък. След като заместим, формулата вече ще изглежда така:

567 = (4 * 5!) + (_ * 4!) + (_ * 3!) + (_ * 2!)  + (_ * 1!)

Продължаваме с делението, но този път делим остатъкът на (N-2)! (в случая това ще е 4!):

87 : (4!) = 87 : 24 = 3 

=> (3 * 24 = 72, остатък 15)

Заместваме във формулата с полученото частно:

567 = (4 * 5!) + (3 * 4!) + (_ * 3!) + (_ * 2!)  + (_ * 1!)

Схванахте идеята. Продължаваме с делението и този път делим предишния остатък на 3! (3 факториел е равно на 6):

15 : (3!) = 15 : 6 = 2

=> (2 * 6 = 12, остатък 3)

Заместваме следващото празно място във формулата с полученото частно:

567 = (4 * 5!) + (3 * 4!) + (2 * 3!) + (_ * 2!)  + (_ * 1!)

Малко остана. Продължаваме делението и сега ще делим 3 на 2 факториел:

3 : (2!) = 3 : 2 = 1

=> (1 * 2 = 2, остатък 1)

Нищо сложно. Сега пак заместваме:

567 = (4 * 5!) + (3 * 4!) + (2 * 3!) + (1 * 2!)  + (_ * 1!)

И най-накрая остава да разделим 1 на 1 факториел (което, разбира се, е равно на 1, но нека да бъдем максимално детайлни 😉):

1 : (1!) = 1 : 1 = 1

=> (остатък 0)

Тъй като стигнахме до деление на 1 факториел, вече остатъкът не ни трябва. Заместваме във формулата и приключваме с тази част от алгоритъма:

567 = (4 * 5!) + (3 * 4!) + (2 * 3!) + (1 * 2!)  + (1 * 1!)

Най-накрая стигнахме до по-вълнуващата част! Сега нека извлечем пермутацията, която ни трябва.

Първо правим едно множество S, което ще съдържа всички възможни елементи на пермутацията. Тъй като N = 6, елементите му ще са от 1 до 6. Създаваме си и едно празно множество P, което ще съдържа самата пермутация:

S = { 1, 2, 3, 4, 5, 6 }

P = ∅

А сега... как да определим кой ще е първият елемент на пермутацията? Нека си добавим финалната версия на горната формула отново, за да е по-прегледно, а и защото ще ни е от огромна полза: 

567 = (4 * 5!) + (3 * 4!) + (2 * 3!) + (1 * 2!)  + (1 * 1!)

От кодирането на пермутации вече знаем, че числото 4 означава, че до първия елемент на търсената пермутация има 4 по-малки елемента от него (стоящи надясно от него). 

Поглеждаме множеството S и правим няколко заключения:

- няма как елементът да е 1, тъй като всички други елементи са по-големи от него

- няма как елементът да е 2, тъй като има само 1 по-малък елемент от него

- няма как елементът да е 3, тъй като има само 2 по-малки елемента от него

- няма как елементът да е 4, тъй като има само 3 по-малки елемента от него

- няма как елементът да е 6, тъй като има 5 по-малки елемента от него

- елементът е 5, тъй като има точно 4 по-малки елемента от него (1, 2, 3 и 4)

Добавяме 5 към P:

S = { 1, 2, 3, 4, 5, 6 }

P = { 5 }

Ще задраскваме всеки елемент от S, който вече сме добавили към множеството на пермутацията, за да няма обърквания.

Продължаваме по същия начин със следващия елемент на пермутацията. От формулата виждаме, че ни трябва елемент, който има 3 по-малки елемента надясно от себе си. От останалите незадраскани елементи в S виждаме, че такъв елемент е 4. Добавяме 4 към P:

S = { 1, 2, 3, 4, 5, 6 }

P = { 5, 4 }

Вече разбрахте как става, но нека да продължим за удоволствие. 😉 Сега ни трябва елемент, който има 2 по-малки елемента надясно от себе си. Такъв елемент ще е 3 (гледаме незадрасканите елементи в S, които отговарят на условието). Добавяме 3 към P:

S = { 1, 2, 3, 4, 5, 6 }

P = { 5, 4, 3 }

Следващият елемент има 1 по-малък елемент надясно от себе си (гледаме формулата). Елементът 2 отговаря на това условие. Добавяме 2 към P:

S = { 1, 2, 3, 4, 5, 6 }

P = { 5, 4, 3, 2 }

Следващият елемент също има 1 по-малък елемент надясно от себе си. Виждаме, че, от останалите елементи, само 6 може да отговаря на това условие. Добавяме 6 към P;

S = { 1, 2, 3, 4, 5, 6 }

P = { 5, 4, 3, 2, 6 }

Остана ни само един елемент, така че няма какво да го мислим толкова - добавяме 1 към P:

S = { 1, 2, 3, 4, 5, 6 }

P = { 5, 4, 3, 2, 6, 1 }

И така, сега в P се съдържа пермутацията, която търсихме толкова време: 5 4 3 2 6 1

Ако искате да се убедите дали резултатът е коректен, опитайте се да я кодирате. 😀

---

Това е за днес! Ако видите някоя неточност - моля кажете ми. 😉