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