Форум: "Потрепаться";
Текущий архив: 2002.10.03;
Скачать: [xml.tar.bz2];
ВнизКнут. Том 1. Глава 1.2.5 Перестанивки и факториалы. Метод 2. Найти похожие ветки
← →
Oleg_Gashev (2002-09-08 22:51) [0]Ну не доходит до меня этот метод. Кто-то может его объяснить более доходчиво?
← →
Старый паскалист (2002-09-08 23:56) [1]Попробую объяснить.
Пусть есть 6 перестановок из n = 3 элементов {123}
123 132 213 231 312 321
Назовём их 3-перестановками (из 3х элементов).
(под числами следует понимать индексы элементов в исходном упорядоченном массиве)
При переходе к n = 4 из каждой 3-перестановки надо получить 4
4-перестановки.
Возьмем одну из них, 231.
И возьмём число k, разбивающее все элементы множества {123} на две группы (>=k и <k) и будем двигать его от начала к концу (for k := 1 to n do...)
На каждой итерации в 3-перестановке 231 числа >=k увеличим на 1, а числа < k оставим прежними.
Таким образом, во всех получившихся комбинациях 342(к=1) 341(к=2) 241(к=3) 231(к=4)
будет отсутствовать само число k.
Так как в исходной 3-перестановке все числа были разные, то от сдвига их некотрого
подмножества вверх все числа останутся разными.
(т.к. любое сдвигаемое число больше любого несдвигаемого, то невозможна
ситуация y+1 = x - для этого у должен быть меньше х)
Выберем любую фиксированную позицию (напр., последнюю) и поставим туда k:
3421(к=1) 3412(к=2) 2413(к=3) 2314(к=4).
Опять же все числа в получившейся перестановке будут разными, т.к. k отсутствовало.
т.е. все эти комбинации будут перестановками {1234}.
Ни одна из этих комбинаций не совпадёт с другой - т.к. на последнем месте у них стоит k,
отличающееся в каждой 4-перестановке.
Теперь, как доказать, что из других 3-перестановок, напр. 123, нельзя получить 4-перестановку,
входящую в число полученных из 231 ?
Предположим, мы получили одинаковую 4-перестановку из разных
3-перестановок.
Очевидно, совпасть могут перестановки только при одинаковом k. Но при известном k мы из 4-перестановки одназначно можем восстановить 3-перестановку - умеьшив все числа > k на 1
и удалив k с фиксированной позиции - следовательно, получаем,
что исходная 3-перестановка была одинаковой, что противоречит
предположению.
Таким образом, из 6 3-перестановок мы получили 6*4 несовпадающих др. с другом 4-перестановок - то есть мы перебрали все возможные перестановки.
(Общее-то их число нам известно)
Вот и всё.
← →
Oleg_Gashev (2002-09-09 00:21) [2]Спасибо. Все более менее понятно.Единственное одно но. Как я понял из алгоритма к нужно ставить для всех троек в одну позицию. В Вашем примере это в конец. Можно и в начало. Алгоритм вроде тоже будет срабатывать.
← →
Старый паскалист (2002-09-09 00:43) [3]Выберем любую фиксированную позицию (напр., последнюю) и поставим туда k:...
Последняя лишь для примера, как и у Кнута.
Выбор позиции никак не влияет на доказательство.
Главное, чтобы для всех перестановок она была одинаковой.
← →
Oleg_Gashev (2002-09-09 00:47) [4]Thanks.
← →
Smiths (2002-09-09 01:20) [5]
> Старый паскалист (08.09.02 23:56)
Респект :)
← →
Старый Паскалист (2002-09-09 11:27) [6]> Smiths
Thanks :)
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.10.03;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.007 c