|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Boris Sivko 2:452/26.14 02 Feb 2003 23:29:08
To : Ivan Merzlyakov
Subject : Все варианты числовой последовательности
--------------------------------------------------------------------------------
Отвечать на письмо на тему "Все варианты числовой последовательности" очень
просто. Это уже сделал Ivan Merzlyakov. о вот когда часы пробили ровно 12:16, а
календарь показывал Воскресенье Февраль 02 2003, настала моя очередь:
IM> Имеем число. Максимальное количество цифр в числе 10. Цифры в числе не
IM> повторяются. Как получить все варианты перестанвок цифр в
IM> числе?
ДДД Цитирую ДДД
Опишем его (при 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. ДДД Конец цитаты ДДД
Счастливо, Ivan. Вспоминай обо мне...
... I'll be back...
* Origin: ГОМЕЛЬ - самый ГОМЕЛЬ в мире! (2:452/26.14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Все варианты числовой последовательности 