Кнут. Том 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. Глава 1.2.5 Перестанивки и факториалы. Метод 2. Найти похожие ветки