2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 
Сообщение27.02.2009, 07:17 
Заслуженный участник


08/04/08
8556
Понятно :-)
Руст!
То есть $S(n) \sim a n^4$ и $a$ - трансцендентно?!
И еще: получается Вы строите перестановку (задаете для нее формулу), сумма на которой не минимальна, но минимальна асимптотически? Я правильно понял?

Коэффициенты численно такие: $b = 0,094541578, a=0,059713900$ (Excel).

 Профиль  
                  
 
 
Сообщение27.02.2009, 08:03 
Заслуженный участник


09/02/06
4382
Москва
Sonic86 писал(а):
Понятно :-)
Руст!
То есть $S(n) \sim a n^4$ и $a$ - трансцендентно?!
И еще: получается Вы строите перестановку (задаете для нее формулу), сумма на которой не минимальна, но минимальна асимптотически? Я правильно понял?

Коэффициенты численно такие: $b = 0,094541578,a=0,059713900$ (Excel).

Да, только расчёты с двойной точностью на Си дали $b=0.0945415777.., \ln(\frac 1b -2)=3-9b, a=b-5.5b^2+12b^3-9b^4=0.0548032...$. a выражается от b как многочлен четвёртой степени, я раньше ошибся в этих коэффициентах.

 Профиль  
                  
 
 
Сообщение27.02.2009, 12:55 
Заслуженный участник


08/04/08
8556
Так выглядит распределение $S$ для $n=4$ при всевозможных перестановках :D

(не получилось вставить диаграмму из Excel - научите :-( )

Для $S=44...100$ значения такие (по порядку):
8 24 24 6 12 6 45 2 24 15 12 45 6 9 12 12 45 9 18 9 6 12 9 9 12 15 30 12 0 8 9 12 15 6 0 6 12 3 2 9 3 12 0 3 0 3 15 0 0 3 0 3 0 3 0 0 1

Что это за распределение?

 Профиль  
                  
 
 
Сообщение02.03.2009, 06:56 
Заслуженный участник


08/04/08
8556
Ура! Мужики! Я прогу написал! Если научусь цитировать, то могу код выложить, на С++. Как и говорил, там тупо m раз локальная оптимизация со случайным поиском, так что значения не точные, а только с вероятностью, только вот не знаю, с какой :-( Я по нескольку сотен испытаний проводил (от 200 до 1000 с ростом n).
$n=1..10$ $S(n)=1; 6; 18; 44; 89; 271; 428; 642; 930$.
$n=11..20$ $S(n)=1304; 1781; 2377; 3111; 4002; 5073; 6345; 7842; 9588; 11610$.
$n=21..30$ $S(n)=13934; 16592; 19613; 23029; 26887; 31179; 35979; 41316; 47223; 53742$.
$n=31..40$ $S(n)=60912; 68776; 77379; 86764; 96979; 108069; 120083; 133075; 147091; 162185$.
$n=41..50$ $S(n)= 178406; 195819; 214472; 234433; 255753; 278496; 302720; 328491; 355878; 384940$.

Можно было бы сделать эмпирическую вероятностную оценку, но без знания распределения это равносильно огромному количеству испытаний, которое (для меня) просто подтвердит факт того, что $S(n)$ равно тому-то. Иначе, чтобы иметь хотя бы общую формулу от n, надо знать распределение $S(n)$, которое генерится алгоритмом, которое, увы, узнать сложнее, чем распределение $S(n)$ само по себе (а само по себе оно довольно сложное). Или надо хотя бы какое-то общее представление о пространстве сумм иметь...

Например, для $n=20$ у меня при 100 испытаниях получилось такое распределение суммы по значениям от 11610 до 11630:
1 4 5 11 11 8 14 6 11 9 8 4 1 0 3 1 1 1 0 1 0
Если 11610 - действительно минимум, то грубо обобщая, можно утверждать, что нескольких сотен испытаний должно хватать. Хотя, конечно, не знаю.
Распределение это, очевидно, не нормальное. Хи-квадрат с этим согласен.

 Профиль  
                  
 
 Re: по следам перестановочного неравенства
Сообщение25.11.2018, 09:55 
Модератор
Аватара пользователя


11/01/06
5660
Sonic86, текущие известные значения $S(17)=6344$ и $S(19)=9587$ меньше полученных вами.

 Профиль  
                  
 
 Re: по следам перестановочного неравенства
Сообщение26.11.2018, 09:05 


20/04/10
1776
Для проверки написал прогу близкую к предложенной Sonic86. Сейчас железо помощнее нежели в девятом году - можно сделать больше оптимизаций на случайно сгенерированных данных. Для каждого $17\leqslant n\leqslant 34$ я делал по $20000$ проверок, вот результаты:
Код:
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17},{16,15,11,12,8,13,4,7,5,10,6,3,2,14,9,17,1},{17,13,12,8,10,5,14,7,9,4,6,11,15,2,3,1,16},6344}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18},{18,16,10,14,9,11,6,12,4,5,7,13,3,8,2,15,1,17},{17,14,15,8,10,7,11,5,13,9,6,3,12,4,16,2,18,1},7842}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19},{19,16,14,12,15,10,5,8,6,9,4,11,3,13,7,17,2,1,18},{18,17,13,11,7,9,15,8,10,6,12,4,14,3,5,2,16,19,1},9587}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},{20,18,16,14,8,9,11,15,10,4,6,5,12,3,7,13,2,17,1,19},{19,17,13,11,15,12,8,5,7,16,9,10,4,14,6,3,18,2,20,1},11610}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21},{20,19,15,12,14,17,6,8,13,9,7,5,4,10,16,11,3,2,18,21,1},{21,18,16,15,10,7,17,11,6,8,9,12,13,5,3,4,14,19,2,1,20},13933}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22},{22,20,18,14,13,11,12,6,15,5,9,17,7,8,3,10,16,4,2,19,1,21},{21,19,15,14,13,12,10,17,6,16,8,4,9,7,18,5,3,11,20,2,22,1},16592}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23},{22,21,19,12,15,14,13,9,17,5,6,11,8,16,4,7,18,3,10,2,20,23,1},{23,20,16,19,12,11,10,13,6,18,14,7,9,4,15,8,3,17,5,21,2,1,22},19612}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24},{24,22,20,18,14,16,9,11,6,15,12,17,4,8,7,5,10,19,3,13,2,21,1,23},{23,21,17,14,15,11,16,12,19,7,8,5,20,9,10,13,6,3,18,4,22,2,24,1},23028}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25},{25,23,20,21,19,12,11,8,10,13,5,14,15,17,7,9,4,16,6,3,18,2,22,1,24},{24,22,19,14,12,16,15,18,13,9,21,7,6,5,11,8,17,4,10,20,3,23,2,25,1},26871}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26},{26,24,22,20,19,14,11,18,12,6,15,5,10,7,8,16,13,4,17,9,21,3,2,23,1,25},{25,23,19,16,14,15,17,9,12,21,8,22,10,13,11,5,6,18,4,7,3,20,24,2,26,1},31178}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27},{26,25,22,18,19,14,17,20,9,10,12,15,5,8,6,13,21,16,4,7,23,11,3,2,24,27,1},{27,24,22,20,15,17,12,9,18,14,11,8,23,13,16,7,4,5,19,10,3,6,21,25,2,1,26},35978}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28},{28,26,24,22,19,18,12,14,11,15,7,17,6,16,9,20,4,10,21,8,13,3,23,5,2,25,1,27},{27,25,22,18,17,15,19,14,16,11,21,8,20,7,12,5,23,9,4,10,6,24,3,13,26,2,28,1},41315}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29},{29,26,25,23,16,17,19,14,11,22,15,10,7,6,13,18,21,8,4,9,12,20,3,24,5,27,2,1,28},{28,27,24,19,22,17,13,16,18,8,11,15,20,21,9,6,5,12,23,10,7,4,25,3,14,2,26,29,1},47223}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30},{30,28,26,22,24,18,13,20,11,15,16,7,8,14,9,17,19,12,21,4,23,6,5,10,3,25,2,27,1,29},{29,27,25,22,16,18,21,12,20,13,11,23,19,10,14,7,6,9,5,24,4,15,17,8,26,3,28,2,30,1},53739}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31},{30,28,27,24,25,23,16,17,20,10,8,22,13,11,7,15,5,12,19,6,9,14,4,18,21,3,26,29,2,31,1},{31,29,26,22,17,15,19,16,12,21,24,8,13,14,20,9,25,10,6,18,11,7,23,5,4,27,3,2,28,1,30},60910}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32},{32,30,28,25,20,23,22,16,13,18,12,14,11,21,7,24,15,5,6,17,10,26,4,8,19,9,3,27,2,29,1,31},{31,29,27,23,24,17,15,19,20,13,18,14,16,8,22,6,9,26,21,7,11,4,25,12,5,10,28,3,30,2,32,1},68776}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33},{33,30,28,26,27,20,16,19,13,21,23,8,11,14,12,10,17,24,5,18,15,6,22,7,25,9,4,29,3,31,2,1,32},{32,31,29,25,19,21,23,17,22,12,10,26,18,13,14,16,9,6,27,7,8,20,5,15,4,11,24,3,28,2,30,33,1},77377}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34},{34,32,30,28,24,21,25,13,15,20,14,9,19,16,11,22,7,17,10,23,26,18,12,6,4,27,8,5,3,29,2,31,1,33},{33,31,29,25,23,22,16,27,21,14,18,26,11,12,17,8,24,9,15,6,5,7,10,19,28,4,13,20,30,3,32,2,34,1},86763}

 Профиль  
                  
 
 Re: по следам перестановочного неравенства
Сообщение08.12.2018, 16:44 


20/04/10
1776
Приведу улучшенные результаты, может быть пригодятся. Увеличив для каждого $n$ число попыток отыскать оптимальное решение и, помимо $swap(a_i,b_j)$, где $a_i, b_j$ элементы одной перестановки, использовав $swap1(a_i, b_j, c_j, d_k)$, где $a_i, b_i$ и $c_j, d_k$ элементы двух различных перестановок, удалось найти решения у которых $S(22)=16591$, $S(26)=31177$, $S(27)=35976$, $S(28)=41314$, $S(29)=47221$, $S(31)=60908$, $S(32)=68774$, $S(33)=77375$, $S(34)=86762$.

Решения:

(Оффтоп)

Код:
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22},
{22,20,18,16,15,11,8,10,13,5,12,4,7,14,3,17,6,9,2,19,1,21},
{21,19,15,13,11,12,14,10,7,16,6,17,9,4,18,3,8,5,20,2,22,1},16591}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26},
{25,24,20,18,19,22,14,11,7,8,15,12,9,13,5,16,4,6,17,21,3,10,2,23,26,1},
{26,23,22,18,14,10,13,15,21,16,8,9,11,7,17,5,19,12,4,3,20,6,24,2,1,25},31177}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27},
{26,24,23,20,18,22,12,15,16,11,6,17,8,7,5,10,14,4,19,9,3,13,21,25,2,27,1},
{27,25,21,18,16,11,17,12,10,13,22,7,14,15,19,9,6,20,4,8,23,5,3,2,24,1,26},35976}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28},
{27,26,24,21,19,17,16,18,10,8,12,9,14,5,15,20,23,11,4,13,6,3,7,22,2,25,28,1},
{28,25,22,19,17,16,14,11,18,20,12,15,9,23,7,5,4,8,21,6,13,24,10,3,26,2,1,27},41314}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29},
{29,26,25,23,21,15,18,10,11,16,20,12,9,6,13,19,8,14,4,22,17,5,3,24,7,27,2,1,28},
{28,27,24,19,17,20,14,22,18,11,8,12,15,21,9,6,13,7,23,4,5,16,25,3,10,2,26,29,1},47221}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31},
{30,28,27,22,24,21,14,19,20,9,13,18,15,25,11,7,8,6,16,5,4,12,23,10,17,3,26,29,2,31,1},
{31,29,26,24,18,17,22,14,12,23,15,10,11,6,13,19,16,20,7,21,25,8,4,9,5,27,3,2,28,1,30},60908}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32},
{32,30,27,24,26,17,21,14,10,20,16,22,9,12,7,18,8,13,11,23,19,15,4,25,5,6,28,3,2,29,1,31},
{31,29,28,24,18,23,16,21,26,12,13,9,20,14,22,8,17,10,11,5,6,7,25,4,19,15,3,27,30,2,32,1},68774}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33},{33,31,29,25,24,22,16,18,13,17,9,19,14,26,21,8,15,12,5,10,20,23,7,27,6,11,4,3,28,2,30,1,32},{32,30,28,25,21,19,23,18,22,15,26,11,14,7,8,20,10,12,27,13,6,5,16,4,17,9,24,29,3,31,2,33,1},77375}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34},{34,32,30,27,28,21,16,22,24,13,15,10,18,14,23,12,6,17,8,20,7,25,5,19,11,4,26,9,3,29,2,31,1,33},{33,31,29,26,20,22,25,16,13,21,17,23,12,14,8,15,28,9,18,7,19,5,24,6,10,27,4,11,30,3,32,2,34,1},86762}

 Профиль  
                  
 
 Re: по следам перестановочного неравенства
Сообщение26.02.2020, 16:16 
Модератор
Аватара пользователя


11/01/06
5660
Свежий препринт по смежной теме:
On a rearrangement inequality of multiple sequences

 Профиль  
                  
 
 Re: по следам перестановочного неравенства
Сообщение02.07.2020, 00:06 


21/05/16
4292
Аделаида
В общем, в статье, которую вы привели, по задаче в этом топике есть лишь одна оценка (снизу) - $n(n!)^{\frac3n}$. Она, конечно, дает погрешность лишь около 1% (для $n=17$ - 0.92, для $n=20$ - 1.2), но...

 Профиль  
                  
 
 Re: по следам перестановочного неравенства
Сообщение03.07.2020, 13:47 
Заслуженный участник


10/01/16
2315
kotenok gav в сообщении #1471627 писал(а):
в этом топике есть лишь одна оценка (снизу) - $n(n!)^{\frac3n}$.

Ну, и по Стирлингу, будет что-то типа $v_{min}\geqslant \frac{n^4}{e^3}$....
Грубую оценку сверху тож можно получить:
Считая перестановки независимыми, для матожидания суммы будем иметь
$E=n(\frac{n+1}{2})^3 \sim \frac{n^4}{8}$. Так что $v_{min}\sim\leqslant \frac{n^4}{8}$
И в мире, где $e=2$, все бы получилось....

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

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



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

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


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

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