Авторското решение използва следния алгоритъм за генериране на пермутации в лексикографски порядък.
(мой превод от книгата The Art of Computer Programming на Donald Knuth, част 4, глава 7.2.1.2)
Сортираме елементите във възходящ ред:
а[0] <= a[1] <= a[2] <= ... <= a[N].
Това ни е първата пермутация.
Всяка слеваща се генерира от следните стъпки:
1. Взимаме индекса на предпоследния елемент: j = N - 1.
Ако a[j] >= a[j + 1] намаляваме j с 1 докато не се изпълни условието
a[j] < a[j + 1]. Ако j < 0 значи няма повече пермутации и прекратяваме изброяването. В този момент j е най-малкия индекс, за който сме посетили всички пермутации, започващи с a[0]...a[j].
2. Взимаме индекса на последния елементо, m = N.
Ако a[j] >= a[m] намаляваме m с 1, докато не се изпълни условието a[j] < a[m]. Разменяме a[j] <-> a[m]. Преди размяната a[j + 1] >= ... >= a[N] следователно a[m] е най-малкият елемент по-голям от a[j] и след като ги разменим се формира следващата лексикографска поредица.
3. Взимаме k = j + 1 и p = N. Докато е изпълнено условието k < p разменяме a[k] <-> a[p] и увеличаваме к с 1, а p намаляваме с 1. Тук идеята е да държим всички елементи след j сортирани възходящо.
Надявам се, че все нещо се разбира 