AlgorithmO #8 — Генериране на пермутации (намиране на следваща пермутация в лексикографски ред)

#dvt32 #algorithms #permutations #lexicographical

(Първо публикувано на 10.01.2017)

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

ОПИСАНИЕ:

Както обяснихме в поста за кодиране на пермутации, те представляват комбинации, при които редът е от значение. Иначе казано, ако имаме множество от 3 елемента и тези елементи са 1, 2 и 3 — пермутациите на това множество ще са 123, 132, 213, 231, 312, 321. Във всяка пермутация трябва да участват всички елементи на множеството.

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

С този алгоритъм можем да генерираме всички съществуващи пермутации — от първата до последната. Или пък ако имаме декодирана пермутацията с номер 345, да намерим тази с номер 346, 347 и т.н, без да се налага да декодираме всяка поотделно.

АЛГОРИТЪМ:

(взето от лекциите ми по Проектиране и анализ на алгоритми :))

Разглеждаме една пермутация на N обекта, означени с числата от 1 до N. Следващата в лексикографското подреждане пермутация се генерира по следния начин:

Преглеждаме пермутацията отдясно наляво докато елементите растат (или са равни, в случай, че има повторения). Спираме на първия елемент, който е по-малък от следващия го. Нека той има номер К.
Измежду елементите, които са отдясно на елемент K, намираме най-малкия, но по-голям от елемента с номер К. Разменяме го с К-тия елемент.
Обръщаме обратно частта от пермутацията с номера К+1…N.

ПРИМЕР:

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

3 2 5 1 7 6 4

Сега искаме да намерим следващата пермутация в лексикографски ред. Как да стане?

Виждаме, че пермутацията се състои от 7 елемента (N = 7). Първото, което трябва да направим, е да номерираме елементите, за да е по-прегледно:

3 2 5 1 7 6 4 (елементи на пермутацията)
1 2 3 4 5 6 7 (номера на елементите)

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

Виждаме, че това е елементът с номер 4 (и стойност 1), понеже директно след него стои по-голям елемент със стойност 7 (за елементите с номера 5, 6 и 7 това не е вярно — до всеки от тях стой по-малък елемент, а до последния елемент няма никакъв друг). В случая ни интересува номерът, а не стойността на елемента.

Стойността на К става номера на елемента, който току що избрахме, т. е K = 4. Нека го означим с удебелен шрифт:

3 2 5 1 7 6 4 (елементи)
1 2 3 4 5 6 7 (номера)

Сега ни трябва най-малкият елемент, който стои отдясно на К-тия елемент и е по-голям от него. Сравнително лесно виждаме, че това е елементът с номер 7 (и стойност 4). Елементите със стойност 7 и 6 също са по-големи от K-тия елемент, но не са минимални.

Нека маркираме и този нов избран елемент с удебелен шрифт:

3 2 5 1 7 6 4 (елементи)
1 2 3 4 5 6 7 (номера)

Следващата стъпка е да разменим местата на тези два елемента (разбира се, номерата им се запазват, разменяме само стойностите):

3 2 5 4 7 6 1 (елементи)
1 2 3 4 5 6 7 (номера)

Последната стъпка е да обърнем наобратно елементите с номера от K+1 до N включително.

Тъй като определихме, че K = 4 и N = 7, това значи, че ще обърнем елементите с номера от 5 до 7 наобратно (т.е. от 7, 6, 1, подредбата им ще стане на 1, 6, 7). Сега пермутацията ще изглежда така: