Вопрос, даже не столько в алгоритмы, сколько в форум "алгебра". Читаю Кнута, том 1, глава 1.2.5 (76 страница). Он рассказывает о перестановках (как из перестановки N элементов изготовить N+1 элемент). Второй метод не понял в принципе. Либо что-то с переводом, либо я просто не понимаю, но получить числа из упражнения №3 (вторым способом) не получается... Может кто объяснит?

P.S. вопрос праздный, просто стало интересно.

Здравствуйте, loknalori, Вы писали:

L>Вопрос, даже не столько в алгоритмы, сколько в форум "алгебра". Читаю Кнута, том 1, глава 1.2.5 (76 страница). Он рассказывает о перестановках (как из перестановки N элементов изготовить N+1 элемент). Второй метод не понял в принципе. Либо что-то с переводом, либо я просто не понимаю, но получить числа из упражнения №3 (вторым способом) не получается... Может кто объяснит?

L>P.S. вопрос праздный, просто стало интересно.

У меня Кнут с непроставленными страницами!

ПРо перестановки: два способа получить что-то из 3124, к примеру.
53124 35124 31524 31254 31245

3124x, x=1,2,3,4,5 --> все i >= x меняем на i+1 --> 42351 41352 41253 31254 31245

Идея второго способа. Если у любой перестановки из n элементов убрать последний, а оставшиеся сместить, так, чтобы были числа от 1 до n-1, то получится перестановка от 1 до n-1. Второй способ делает все наоборот. ПРи этом мы всегда получим разные перестановки (как это понять? проще всего так: из (n-1)! данных перестановок мы получим заведомо n! перестановок, кроме того, любую перестановку из n элементов так можно получить, т.е. мы получаем все и по одному разу).

Здравствуйте, loknalori, Вы писали:

L>Вопрос, даже не столько в алгоритмы, сколько в форум "алгебра". Читаю Кнута, том 1, глава 1.2.5 (76 страница). Он рассказывает о перестановках (как из перестановки N элементов изготовить N+1 элемент). Второй метод не понял в принципе. Либо что-то с переводом, либо я просто не понимаю, но получить числа из упражнения №3 (вторым способом) не получается... Может кто объяснит?

Имеется ввиду следующее:
Пусть есть перестановка (2 3 1). Допишем к ней n чисел вида (n — 1/2)
Получим (2 3 1 1/2); (2 3 1 3/2) и т.д.
Теперь заменяем каждый элемент перестановки на его порядковый номер по возрастанию. То есть для (2 3 1 1/2) имеем: 1/2 — самое маленькое, соответственно заменяется на единицу, 1 — на двойку и т.д. Получаем (3 4 2 1).

Для (3 1 2 4) и чисел {12345} имеем:
(3 1 2 4 1/2); (3 1 2 4 3/2); (3 1 2 5/2); (3 1 2 4 7/2); (3 1 2 4 9/2)

заменяем:
(4 2 3 5 1) (4 1 3 5 2) ; дальше влом, с ответом сходится.