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

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

Какво представляват пермутациите? Общо взето, те са комбинации, при които редът на елементите има значение.

Харесва ми обяснението предоставено от MathIsFun - ако кажем "плодовата ми салата съдържа ябълки, грозде и банани", редът на елементите няма значение (можем лесно да кажем, че салатата съдържа "банани, ябълки и грозде" и твърдението пак ще е валидно) и тогава говорим за комбинация.

Но ако редът има значение, например когато кажем "PIN кодът на телефона ми е 1337", тогава говорим за пермутация, тъй като не би било правилно да кажем, че кодът е 1373 или някакво друго число.

Тук ще говорим за пермутации без повторения на елементите, така че ако става дума за пермутации от 3 елемента, валидни биха били пермутациите 123, 132, 213, 231, 312, 321, но НЕ и 112 (имаме повторение на елемент 1) и 134 (няма елемент 4, ако приемем, че трите елемента са 1, 2 и 3).

Една пермутация трябва да включва всички елементи на даденото множество. И, както казахме, редът на елементите е от значение.

---

Идеалното изображение за този пост. :)

ОПИСАНИЕ:

Всяко N-елементно множество има N! (N факториел) на брой пермутации.

N! = 1 * 2 * ... * N

Понякога е полезно да "кодираме" дадена пермутация като я означим с някакво число (за да може по-късно да я декодираме).

Реално това кодиране представлява определянето на номера на пермутацията в лексикографския ред на всички пермутации от N елемента.

АЛГОРИТЪМ:

1. Определяме броя на на елементите в множеството (N)
2. Кодираме по следната "формула":

x[i] * (N-1)! + x[i+1] * (N-2)! + ... + x[N] * 1!

... където x[i] е броят елементи, които са по-малки от елемента, стоящ на позиция 'i' в пермутацията, и са надясно от него.

Номерацията на елементите започва от 1.

ПРИМЕР:

Нека имаме пермутацията:

2 5 3 1 4

Бързо виждаме, че тази пермутация, се образува от множество с 5 елемента (N = 5), което означава, че броят на пермутациите е 5! (N! = 5! и 5! = 120).

Първата стъпка е да определим колко са елементите, които са по-малки от 2 и стоят надясно от него.

2 5 3 1 4

По-малък e само елементът 1. Следователно имаме 1 елемент, който отговаря на горното условие.

Умножаваме 1 (броят на елементите, отговарящите на условието, а НЕ стойността на елемента) по (N-1)! и понеже установихме, че N = 5, правим следното изчисление:

1 * 4!

Продължаваме към следващия елемент, 5:

2 5 3 1 4

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

(1 * 4!) + (3 * 3!)

Следващият елемент е 3: 

2 5 3 1 4

По-малък е само елементът 1 (1 елемент). Умножваме 1 по (N-3)! и добавяме към предишната изчислена сума:

(1 * 4!) + (3 * 3!) + (1 * 2!)

И накрая остана елементът 1 (4 няма да го разглеждаме, тъй като е последен и съответно няма елементи, които отговарят на условието в алгоритъма):

2 5 3 1 4

Доста жалко, но 4 не е по-малък елемент от 1 и съответно имаме 0 елемента, които отговарят на условието. Умножаваме по (N-4)! и добавяме към предишната изчислена сума (разбира се, тъй като умножаваме по 0, реално няма смисъл да добавяме 0 към предишната сума, но пък така алгоритъмът става по-ясен 😉):

(1 * 4!) + (3 * 3!) + (1 * 2!) + (0 * 1!)

Стигнахме до края и сега остава само да пресметнем тази сума.

Получаваме 24 + 18 + 2 = 44.

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

---

Това е за днес! Утре ще ви покажа как става и декодирането. Ако видите някоя неточност, моля кажете ми! 😉