Генератор перестановок. (Без доказательства)

Генератор перестановок. (Без доказательства)

1. Располагаем исходную перестановку в порядке убывания. (n … 321)

2. Находим наименьший индекс i, iÍ{2..n},при котором a_i_-1>a_i

3. Находим наименьший индекс j, jÍ{1,2,…i-1},при котором a_j>a_i

4. Меняем местами a_j и a_i

5. Вычислим k=[^i-1/₂]. Если к=0, то ничего не делаем. Если к¹0, то меняем местами компоненты в парах: (a₁,a_i_-1), (a₂,a_i_-2), … , (a_k,a_i_-_k).

6. Выводим перестановку и если она больше чем 123 … n, то возвращаемся к шагу 2. (или завести счетчик перестановок, он должен быть равен n!)

Пример

1) 321 i=2, k=0

2) 231 i=3, k=1

132

3) 312 i=2, k=0

4) 132 i=3, k=1

123

5) 213 i=2, k=0

6) 123