Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 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
1-8045
Itap
2002-09-22 15:58
2002.10.03
Быстрый поиск в RichEdit


1-7937
kex86
2002-09-24 01:34
2002.10.03
ХР


1-7989
Melnyk
2002-09-20 14:53
2002.10.03
Как изменить имя логического диска


7-8207
Smallll
2002-07-23 18:37
2002.10.03
Как програмно узнать температуру процессора?


3-7823
Serg2002
2002-09-12 10:30
2002.10.03
Супер сложный запрос :)





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский