помогите разобраться с Кнутом.

← →
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.

напиши под второй из новых последовательностей числа от 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;

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

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

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

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

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