Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2007.05.27;
Скачать: CL | DM;

Вниз

помогите разобраться с Кнутом.   Найти похожие ветки 

 
guestfromwwww   (2007-04-24 19:12) [0]

глава 1.2.5. перестановки и фракталы. том 1. стр 68

Метод 2. Для каждой перестановки A1A2...An-1 из {1,2...,n-1} объектов построим еще n перестановок следующим образом. Сначала построим наборъ
A1A2...An-1 1/2, A1A2...An-1 3/2,  ..., A1A2...An-1(n - 1/2).

Затем заменим элементы каждой перестановки цифрами {1,2,...,n}, сохраняя порядок. Например,  для перестановки 231 из (3) получим
 231 1/2, 231 3/2, 231 5/2, 231 7/2

и после замены получим 3421, 3412, 2413, 2314.

как это понять? что там делать с дробями?


 
oldman ©   (2007-04-24 19:14) [1]


> Сначала построим наборъ


Это точно Кнут?
А че уж без ять и ижици?


 
кввв   (2007-04-24 19:17) [2]

А что он тебе сделал?


 
oldman ©   (2007-04-24 19:18) [3]


> и после замены получим 3421, 3412, 2413, 2314.


А вот еще про "замену" можно выдержку?


 
guestfromwwww   (2007-04-24 19:19) [4]

печатаю без русской клавиатуру.Sorry


 
oldman ©   (2007-04-24 19:24) [5]


> oldman ©   (24.04.07 19:18) [3]
>
> > и после замены получим 3421, 3412, 2413, 2314.
>
>
> А вот еще про "замену" можно выдержку?


Потому, что до этой строки все понятно.
А вот, что там за "замена" у Кнута - фиг его знает...


 
guestfromwwww   (2007-04-24 19:24) [6]


> А вот еще про "замену" можно выдержку?


это всё. дальше идет еще один способ описания этого процесса.


 
MBo ©   (2007-04-24 20:03) [7]

эти дроби по большому счету -  просто способ указать место вставки между элементами перестановки меньшего ранга.
На примере Кнута - имеется перестановка 3-х элементов 2, 3, 1, дописываем числа от 1/2 до 4-1/2
2 3 1 0.5
2 3 1 1.5
2 3 1 2.5
2 3 1 3.5
и перенумеруем каждую из последовательностей по возрастанию числами от 1 до 4, например, вторая строка станет 3 4 1 2


 
MBo ©   (2007-04-24 20:05) [8]

P.S. про место вставки - не в тему.
Это метод переранжирования.


 
oldman ©   (2007-04-24 20:07) [9]


> MBo ©   (24.04.07 20:03) [7]


Вообще-то, для 3-х элементов перестановок должно быть 6, а не 4.


> и после замены получим 3421, 3412, 2413, 2314.


А куда делось "1432, 1423"???


 
oldman ©   (2007-04-24 20:08) [10]


> глава 1.2.5. перестановки и фракталы. том 1. стр 68


А может где-то раньше про "замену" говорилось?
Кнута не надо читать с 68-ой страницы. Вредно.


 
MBo ©   (2007-04-24 20:12) [11]

>Вообще-то, для 3-х элементов перестановок должно быть 6, а не 4.

Взята одна перестановка из трех элементов, и на ее основе сгенерированы 4 перестановки из 4-х элементов, то же самое и с остальными пятью - итого получится 24 перестановки из 4-х элементов


 
oldman ©   (2007-04-24 20:14) [12]


> MBo ©   (24.04.07 20:12) [11]


Пойти Кнута перечитать, что ли?
:)))


 
guestfromwww   (2007-04-25 00:55) [13]


> и перенумеруем каждую из последовательностей по возрастанию
> числами от 1 до 4, например, вторая строка станет 3 4 1 2
> 2
>


Это как? Можно пример на пальцах.  Да, если можно как эта операция называеться по английски. Или исходник на C или Pascal.


 
MBo ©   (2007-04-25 05:16) [14]

напиши под второй из новых последовательностей числа от 1 до 4 соответственно их величине
2 3 1 1.5
3 4 1 2

другой способ - поскольку к каждой из N последовательностей добавляется дробь i-1/2, то можно одним проходом увеличивать на 1 числа, меньшие i, заменять дробь на i, а меньшие i числа не трогать, примерно так:

for np := 1 to (n-1)! do
    for i := 1 to n do begin
         for k := 1 to n - 1 do
             if P[np, k] < i then
                 Inc(P[np, i])
         P[np, i] := i;
     end;    


 
default ©   (2007-04-25 08:24) [15]

суть не в методе получения, метод получения - это механика
суть в том как можно было придти к такому методу, какие он даёт выигрыши и доказательство неповторимости перестановок


 
MBo ©   (2007-04-25 09:16) [16]

>  P[np, i] := i;
 P[np, n] := i;


 
oldman ©   (2007-04-25 10:34) [17]


> default ©   (25.04.07 08:24) [15]


А ведь действительно, что для 231 перестановок всего 4
А хочется больше. Много больше...



Страницы: 1 вся ветка

Текущий архив: 2007.05.27;
Скачать: CL | DM;

Наверх




Память: 0.5 MB
Время: 0.034 c
15-1177679014
SergeyLTD
2007-04-27 17:03
2007.05.27
Помогите, пожалуйста, с лабораторными работами


3-1173172482
VadimSpb
2007-03-06 12:14
2007.05.27
Скорость поиска


11-1160134748
Thaddy
2006-10-06 15:39
2007.05.27
tip to reduce memory when inactive.


6-1164042005
IgneouS
2006-11-20 20:00
2007.05.27
Что лучше?


15-1176890619
Ломброзо
2007-04-18 14:03
2007.05.27
Ещё один гвоздик в гробик