Решение задачи 1.
Этот алгоpитм хорошо известен и достаточно подробно изложен. Опишем его (при N=5), от чего рассуждения не утратят общности. Алгоритм составлен так, что в процессе его исполнения перестановки N чисел располагаются лексикографически (в словарном порядке). Это значит, что перестановки сравниваются слева направо поэлементно. Больше та, у которой раньше встретился элемент, больше соответствующего ему элемента во второй перестановке. (Например, если S=(3,5,4,6,7),а L=(3,5,6,4,7), то S<L).
Принцип работы алгоритма разъясним на примере. Допустим, необходимо воспpоизвести все перестановки цифр 3,4,5,6,7. Первой перестановкой считаем перестановку (3,4,5,6,7). Последней воспроизводимой перестановкой будет (7,6,5,4,3).
Предположим, что на некотором шаге работы алгоритма получена перестановка
P=(5,6,7,4,3).
Для того чтобы определить непосредственно следующую за ней перестановку, необходимо, пересматривая данную перестановку справа налево, следить за тем, чтобы каждое следующее число было больше предыдущего, и остановиться сразу же, как только это правило нарушится. Место останова указано стрелкой:
(5,6,7,4,3).
-
Затем вновь просматриваем пройденный путь ( справа налево ) до тех пор, пока не дойдем до первого числа, которое уже больше отмеченного. Ниже место второго останова отмечено двойной стрелкой.
(5,6,7,4,3).
- Э
Поменяем местами отмеченные числа:
(5,7,6,4,3).
Э -
Теперь в зоне, расположенной справа от двойной стрелки, упорядочим все числа в порядке возрастания. Так как до сих пор они были упорядочены по убыванию , то это легко сделать, перевернув указанный отрезок. Получим:
Q=(5,7,3,4,6).
Q и есть та перестановка, которая должна воспроизводиться непосредственно после P.
Действительно, P<Q, так как, пересматривая эти перестановки слева направо, (P(2)=6,Q(2)=7). Пусть существует такая перестановка R, что P<R<Q. Тогда P(1)=R(1)=Q(1). По построению же Q(2) -- это наименьшее во множестве Q\Q(1)={3,4,6,7} число, такое, что Q(2)>P(2). Поэтому для R(2) верно одно из двух равенств: R(2)=Q(2) или R(2)=P(2). Но так как в P элементы, начиная с P(3), убывают, то из P<R следует, что если P(2)=R(2), то и P=R. Аналогично, так как в Q элементы, начиная с Q(3), возрастают, то из R<Q следует, что если R(2)=Q(2), то и R=Q.
|
