2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Распределение порядка во всех перестановках
Сообщение13.10.2009, 12:19 


13/10/09
283
Ukraine
В процессе реализации алгоритма сортировки естественным слиянием возникла следующая несложная комбинаторная задача. Может, кто подскажет ее решение.

Дано множество всех перестановок натуральных чисел от 1 до n. Сколько в них будет упорядоченных (по возрастанию или убыванию) подпоследовательностей длины $Q_n(k)$ для $1 \leqslant k \leqslant n$? Случай $k = 1$ будем рассматривать только для тех перестановок, которые дают «зависшую» подпоследовательность длины 1 в конце перестановки. Порядок подпоследовательностей рассматривается относительно начала перестановки. Подпоследовательности рассматриваются до тех пор, пока сохраняется их локальный порядок и не пересекаются между собой. Также интересует средняя длина таких упорядоченных подпоследовательностей.

Очевидно, что $Q_n(n) = 2$. Но для остальных k формулы, очевидно, будут сложнее.

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 12:38 
Заблокирован по собственному желанию
Аватара пользователя


18/05/09
3612
Только подсказки по набору формул.

Не надо вставлять [mаth]...[/mаth]. Тэги вставятся автоматически при интрерпретации сообщения. Необходимо (и достаточно) окружить формулу знаками доллара: $ Q_n(n-m) $ --- $ Q_n(n-m) $.
$ 2< k \le n$ --- $ 2< k \le n$ (команды \le, \ge).

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 12:50 


13/10/09
283
Ukraine
AKM в сообщении #251280 писал(а):
Только подсказки по набору формул.

Не надо вставлять [mаth]...[/mаth]. Тэги вставятся автоматически при интрерпретации сообщения. Необходимо (и достаточно) окружить формулу знаками доллара: $ Q_n(n-m) $ --- $ Q_n(n-m) $.
$ 2< k \le n$ --- $ 2< k \le n$ (команды \le, \ge).

Понял, спасибо :) .

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 12:50 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Мне больше нравится $\geqslant$ и $\leqslant$ .
Вопрос к Scholium: подпоследовательности одной перестановки могут пересекаться? Подпоследовательность - это члены последовательности, идущие подряд по номерам или возможны разрывы?

Например, для перестановки $12345$ сколько подпоследовательностей длины 3?
$123\quad 234 \quad 345$ или только одна из них?
$134$ не считается?

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 13:05 


13/10/09
283
Ukraine
gris в сообщении #251284 писал(а):
Мне больше нравится $\geqslant$ и $\leqslant$ .
Вопрос к Scholium: подпоследовательности одной перестановки могут пересекаться? Подпоследовательность - это члены последовательности, идущие подряд по номерам или возможны разрывы?

Например, для перестановки $12345$ сколько подпоследовательностей длины 3?
$123\quad 234 \quad 345$ или только одна из них?
$134$ не считается?

Спасибо насчет знаков неравенств!

В последовательности 12345 нет подпоследовательностей длины 3, так как здесь есть только одна подпоследовательность длины 5! Соответственно никаких пересечений не предусматривается. Задача появилась в алгоритме сортировки, в котором последовательно с начала произвольной перестановки выбирались упорядоченные (в любом порядке) подпоследовательности, пока они не заканчивались. У меня опубликован демонстрационный алгоритм этой сортировки (ее нелинейный вариант), если интересно могу дать ссылку. Кстати эксперименты со случайными последовательностями натуральных чисел показали, что средняя длина упорядоченных подпоследовательностей лежит в пределах от 2.41 до 2.42. Но хотелось бы найти это число теоретически.

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 13:11 
Заслуженный участник


09/08/09
3438
С.Петербург
А в последовательности 14325 есть возрастающая подпоследовательность длины 3? 135 с разрывами считается?

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 13:12 
Заслуженный участник
Аватара пользователя


14/02/07
2648
Пусть $\mathcal N$ - семейство наборов номеров, по которым мы берем подпоследовательность.

Удобно писать в первом случае
$$
S_N = \sum_{N\in \mathcal N} I_{N\text{-подпоследовательность монотонна}}.
$$
и во втором случае
$$
L_N = \frac{1}{|\mathcal N|}\sum_{N\in \mathcal N} |N|I_{N\text{-подпоследовательность монотонна}}.
$$
Тогда, например, в первом случае
$$
E[S_N] = \sum_{N\in \mathcal N} \frac{1+1_{|N|\ge 2}}{|N|!},
$$
во втором:
$$
E[L_N] = \frac{1}{|\mathcal N|}\sum_{N\in \mathcal N} \frac{1+1_{|N|\ge 2}}{(|N|-1)!}
$$

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 13:23 


25/05/09
231
Тогда осталось непонимание про последовательность в форме W: 52314 это 4 подпоследовательности длины 2 или две,и если 2 то какие? Это же влияет на статистику

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 13:31 


13/10/09
283
Ukraine
Maslov в сообщении #251286 писал(а):
А в последовательности 14325 есть возрастающая подпоследовательность длины 3? 135 с разрывами считается?

В этой последовательности будет три упорядоченных подпоследовательности:
14, 32 и 5, соответственно две подпоследовательности длины 2 и одна 1.

nn910 в сообщении #251289 писал(а):
Тогда осталось непонимание про последовательность в форме W: 52314 это 4 подпоследовательности длины 2 или две,и если 2 то какие? Это же влияет на статистику

Смотрите, мы имеем объединение упорядоченных подпоследовательностей: $52314 = 52 + 31 + 4$.

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 13:39 
Заслуженный участник


09/08/09
3438
С.Петербург
Scholium в сообщении #251291 писал(а):
Maslov в сообщении #251286 писал(а):
А в последовательности 14325 есть возрастающая подпоследовательность длины 3? 135 с разрывами считается?

В этой последовательности будет три упорядоченных подпоследовательности:
14, 32 и 5, соответственно две подпоследовательности длины 2 и одна 1.
Извините, что-то мне логику никак не уловить. А 432 почему не считаем?

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 13:45 


13/10/09
283
Ukraine
Хорхе в сообщении #251287 писал(а):
Пусть $\mathcal N$ - семейство наборов номеров, по которым мы берем подпоследовательность.

Удобно писать в первом случае
$$
S_N = \sum_{N\in \mathcal N} I_{N\text{-подпоследовательность монотонна}}.
$$
и во втором случае
$$
L_N = \frac{1}{|\mathcal N|}\sum_{N\in \mathcal N} |N|I_{N\text{-подпоследовательность монотонна}}.
$$
Тогда, например, в первом случае
$$
E[S_N] = \sum_{N\in \mathcal N} \frac{1+1_{|N|\ge 2}}{|N|!},
$$
во втором:
$$
E[L_N] = \frac{1}{|\mathcal N|}\sum_{N\in \mathcal N} \frac{1+1_{|N|\ge 2}}{(|N|-1)!}
$$

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

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 13:48 
Заслуженный участник


09/08/09
3438
С.Петербург
Мы что, просто разбиваем каждую перестановку на "отрезки монотонности"?

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 13:59 


13/10/09
283
Ukraine
Maslov в сообщении #251293 писал(а):
Scholium в сообщении #251291 писал(а):
Maslov в сообщении #251286 писал(а):
А в последовательности 14325 есть возрастающая подпоследовательность длины 3? 135 с разрывами считается?

В этой последовательности будет три упорядоченных подпоследовательности:
14, 32 и 5, соответственно две подпоследовательности длины 2 и одна 1.
Извините, что-то мне логику никак не уловить. А 432 почему не считаем?

Во-первых, мы идем сначала (слева направо), во-вторых, подпоследовательность выбираем до тех пор, пока существует ее локальный порядок и, в-третьих, подпследовательности не должны пересекаться. Смотрите, после единицы четверка образует локальное возрастание, а тройка дает локальное убывание. Отсекаем возрастание 14 и начинаем процедуру заново к оставшейся подпоследовательности 325. Здесь порядок начинается с убывания – 32. Пятерка нарушает этот порядок, она остается после отсечения 32 от 325. Таким образом, получаем «равенство»: 14325 = 14 + 32 + 5.

-- Вт окт 13, 2009 15:02:19 --

Для лучшего восприятия можно посмотреть мою тему: «Нелинейная demo реализация сортировки естественным слиянием (Natural Merge Sort) на Visual FoxPro» на:
http://sql.ru/forum/actualthread.aspx?bid=24&tid=686605&pg=2 .

-- Вт окт 13, 2009 15:10:34 --

Maslov в сообщении #251296 писал(а):
Мы что, просто разбиваем каждую перестановку на "отрезки монотонности"?

Ну, да! Я же говорю, что задача не должна быть сложной. Только мы рассматриваем эти «отрезки монотонности» (для убывающей и неубывающей подпоследовательностей) на всем множестве, всех перестановок натуральных чисел от 1 до n. Общее количество таких перестановок равно n! . Нам надо подсчитать количество всех подпоследовательностей заданной длины k и среднюю длину такой подпоследовательности, которая экспериментально определена в пределах от 2,41 до 2,42.

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 14:41 
Заслуженный участник
Аватара пользователя


14/02/07
2648
Scholium в сообщении #251294 писал(а):
Ну, это больше похоже на определения, чем на вычисления, к тому же, не совсем понятны обозначения.

После ваших объяснений, как оно на самом деле должно формулироваться, уже не важно. Не так страшно, что вы не пишете внятную постановку задачи сразу же, как то, что вы не извиняетесь за то, что вы этого не сделали. Не украшает такое поведение.

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение13.10.2009, 15:24 


13/10/09
283
Ukraine
Хорхе в сообщении #251308 писал(а):
Scholium в сообщении #251294 писал(а):
Ну, это больше похоже на определения, чем на вычисления, к тому же, не совсем понятны обозначения.

После ваших объяснений, как оно на самом деле должно формулироваться, уже не важно. Не так страшно, что вы не пишете внятную постановку задачи сразу же, как то, что вы не извиняетесь за то, что вы этого не сделали. Не украшает такое поведение.

К сожалению, я не понимаю ваших эмоций. Два человека одно и тоже событие видят по разному. Для меня формулировка задачи в теме была и остается достаточно понятной, но в любом случае дополнительные объяснения неизбежны, хотя бы потому, что задача новая и формулировка еще не «утряслась». За что ж тут извиняться? Вы всегда формулируете новые утверждения без дальнейшей правки? Думаю, что не надо быть слишком требовательным к другим, ибо люди не идеальны и никогда не будут таковыми. Так что давайте, без взаимных упреков :) .

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group