2014 dxdy logo

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

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


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


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

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 11  След.
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 17:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Если мы возьмём самую первую цепочку

Код:
11  23  29  59  1361  2663  2693  2699  2711

то все следующее цепочки из приведённых до многоточия мы уже не можем к ней пибавить.
А цепочку
Код:
1151  1163  1223  1283  1361  1439  1499  1559  1571

можем прибавить.
И далее до конца массива больше ни одну цепочку прибавить не можем.
Вот это будут две цепочки. Надо к ним ещё две добавить.

Как выбирать визуально цепочки из всей базы цепочек, я понимаю. Как написать программу пока не понимаю.
Может, кто-нибудь подскажет?

Вообще у меня ощущение, что я ошиблась разделом:-(

-- Сб июн 13, 2015 18:34:05 --

Если мы разделим первые 40 чисел массива на 10 групп по 4 числа в группе:

Код:
1. 11 23 29 59
2. 89 101 113 131
3. 173 179 191 263
4. 281 311 383 389
5. 449 479 509 569
6. 593 641 653 659
7. 683 719 743 773
8. 809 821 911 1013
9. 1103 1109 1151 1163
10. 1223 1229 1283 1289

и будем комбинировать по 4 группы из этого набора групп, мы получим 210 нужных наборов цепочек.

Например, такой набор:

Код:
11 23 29 59 1361 2663 2693 2699 2711
89 101 113 131 1361 2591 2609 2621 2633
173 179 191 263 1361 2459 2531 2543 2549
281 311 383 389 1361 2333 2339 2411 2441

Но ведь это далеко не все варианты! Малая толика.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 19:00 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А теперь разделим так перве 40 чисел массива на 10 групп по 4 числа:

Код:
1. 23 29 59 89
2. 101 113 131 173
3. 179 191 263 281
4. 311 383 389 449
5. 479 509 569 593
6. 641 653 659 683
7. 719 743 773 809
8. 821 911 1013 1103
9. 1109 1151 1163 1223
10. 11 1229 1283 1289

и снова будем комбинировать, как выше написано.
Получим ещё 210 нужных наборов цепочек. Правильно?

Сколько же раз будет по 210? И исчерпаются ли этим все варианты наборов цепочек??

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 19:33 


17/04/15
46
Nataly-Mak в сообщении #1026748 писал(а):
Если мы возьмём самую первую цепочку

Код:
11  23  29  59  1361  2663  2693  2699  2711

то все следующее цепочки из приведённых до многоточия мы уже не можем к ней прибавить.
А цепочку
Код:
1151  1163  1223  1283  1361  1439  1499  1559  1571

можем прибавить.
И далее до конца массива больше ни одну цепочку прибавить не можем.
Вот это будут две цепочки. Надо к ним ещё две добавить.

Цепочку
Код:
89  101  113  131  1361 2591  2609  2621  2633

можно прибавить?

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 19:40 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
DanilovV в сообщении #1026780 писал(а):
Цепочку
Код:
89  101  113  131  1361 2591  2609  2621  2633

можно прибавить?

Да, можно.
Ориентируемся по первым четырём числам цепочки (вторая часть цепочки - комплементарные числа, с ними автоматически будет всё в порядке).

И ещё: все цепочки должны быть нормализованные, то есть числа в них должны быть расположены в порядке возрастания.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 19:58 


17/04/15
46
Тогда к любой цепочке можно добавить ~50000 цепочек

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 20:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А вы можете ответить точно на поставленный вопрос: сколько всего будет нужных наборов из 4-х цепочек?

Я выше показала, как могу "живьём" представить 420 наборов.

Вот и вы расскажите, пожалуйста, сколько "живых" наборов цепочек вы можете представить.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 20:19 


17/04/15
46
Nataly-Mak в сообщении #1026785 писал(а):
А вы можете ответить точно на поставленный вопрос: сколько всего будет нужных наборов из 4-х цепочек?

Я выше показала, как могу "живьём" представить 420 наборов.

Вот и вы расскажите, пожалуйста, сколько "живых" наборов цепочек вы можете представить.

Сколько нужно из 8 триллионов возможных наборов?

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 20:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
DanilovV в сообщении #1026790 писал(а):
Сколько нужно из 8 триллионов возможных наборов?

Извините, я не поняла ваш вопрос.

Мне нужен точный ответ: наборов цепочек, удовлетворяющих всем нужным свойствам, будет столько-то (точное число).
Я не знаю, как подсчитать число таких наборов. Поэтому спрашиваю.

Вы хотите сказать, что всего наборов будет 8 триллионов?
Код программы можете показать, которая формирует и подсчитывает эти наборы?

-- Сб июн 13, 2015 21:29:53 --

Может быть, наборов будет 62852101650 :?: (число сочетаний из 40 по 16)

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 20:31 


17/04/15
46
Nataly-Mak в сообщении #1026793 писал(а):
DanilovV в сообщении #1026790 писал(а):
Сколько нужно из 8 триллионов возможных наборов?

Извините, я не поняла ваш вопрос.

Мне нужен точный ответ: наборов цепочек, удовлетворяющих всем нужным свойствам, будет столько-то (точное число).
Я не знаю, как подсчитать число таких наборов. Поэтому спрашиваю.

Вы хотите сказать, что всего наборов будет 8 триллионов?
Код программы можете показать, которая формирует и подсчитывает эти наборы?

Ошибся при наборе в калькуляторе:
40!/24!/(24)^4=3963642086353950000
И как будет проверятся программа, если в ней где-то вкралась ошибка? :lol:

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 20:34 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
DanilovV в сообщении #1026794 писал(а):
И как будет проверятся программа, если в ней где-то вкралась ошибка? :lol:

Программа, вообще-то, проверяется по логике, то бишь по алгоритму.
Далее, программу проверяют по первым N результатам. Если они неправильные (что обнаружить нетрудно), значит, программа врёт.

-- Сб июн 13, 2015 21:37:52 --

Дамы и господа!
Есть уже два варианта ответа на вопрос:

Код:
62852101650
40!/24!/(24)^4=3963642086353950000

Кто больше? :D

-- Сб июн 13, 2015 21:56:46 --

Обоснование моего ответа.
Набор цепочек:

Код:
11 23 29 59 1361 2663 2693 2699 2711
89 101 113 131 1361 2591 2609 2621 2633
173 179 191 263 1361 2459 2531 2543 2549
281 311 383 389 1361 2333 2339 2411 2441

характеризуется 16-ю различными числами (первые 4 числа в каждой цепочке).
Всего у нас чисел в массиве 40 (первые числа из комплементарных пар).
Следовательно, все сочетания из 40 по 16 дадут нам все возможные наборы из 4-х цепочек.

Где ошибка в моих рассуждениях :?:

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 21:04 


17/04/15
46
Nataly-Mak в сообщении #1026797 писал(а):
]
Обоснование моего ответа.
Набор цепочек:

Код:
11 23 29 59 1361 2663 2693 2699 2711
89 101 113 131 1361 2591 2609 2621 2633
173 179 191 263 1361 2459 2531 2543 2549
281 311 383 389 1361 2333 2339 2411 2441

характеризуется 16-ю различными числами (первые 4 числа в каждой цепочке).
Всего у нас чисел в массиве 40 (первые числа из комплементарных пар).
Следовательно, все сочетания из 40 по 16 дадут нам все возможные наборы из 4-х цепочек.

Где ошибка в моих рассуждениях :?:

Но эти 16 элементов тоже можно потасовать.
Например первые четверки в двух наборах
Код:
11 29 59 113
23 89 101 131

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 21:12 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Цитата:
Следовательно, все сочетания из 40 по 16 дадут нам все возможные наборы из 4-х цепочек.

Нет, наверное, это неправильно :-(

Ещё надо посчитать, сколькими способами 16 чисел можно распределить по 4-м цепочкам.

DanilovV
а вы что-то хотели сказать? :-)

А, уже вижу, что хотели сказать. Но я это уже и сама поняла. Да, можно потасовать.
Так сколькими же способами можно потасовать?

-- Сб июн 13, 2015 22:16:28 --

У меня получается, что потасовать можно 1820 способами. Правильно?

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 21:22 


17/04/15
46
Nataly-Mak в сообщении #1026810 писал(а):
-- Сб июн 13, 2015 22:16:28 --

У меня получается, что потасовать можно 1820 способами. Правильно?

Откуда взялось 1820?
У меня получается $16*15*14*13$ способов составить первую четверку и т.д
Всего $16!$ способов, а так как порядок не важен, то делим на $24*24*24*24$
Итого 63063000 способов

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение13.06.2015, 21:49 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
DanilovV в сообщении #1026816 писал(а):
Откуда взялось 1820?

Имеем 16 различных чисел:

Код:
1, 2, 3, ..., 16

Надо сделать все возможные наборы по 4 различных числа.
Я посчитала, что их будет: число сочетаний из 16 по 4.
Неправильно?

-- Сб июн 13, 2015 23:17:20 --

А в ответ - тишина... (с) :D

Хорошо, завтра на свежую голову возьму первые 16 чисел массива и попробую из них составить все "живые" наборы по 4 цепочки.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение14.06.2015, 09:36 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #1026797 писал(а):
Есть уже два варианта ответа на вопрос:

Код:
62852101650
40!/24!/(24)^4=3963642086353950000

Кто больше? :D
Ответом будет мультиномиальный коэффициент:$$\binom{40}{24,4,4,4,4}=\frac{40!}{24!\ 4!\ 4!\ 4!\ 4!}=\frac{40!}{24!\ 24^4}=3\ 963\ 642\ 086\ 353\ 950\ 000$$Почти четыре квинтиллиона вариантов.

P.S. в русской Википедии ошибка — разбиения должны браться без учёта порядка в каждом блоке. Правильное определение здесь.

-- 14 июн 2015, 09:57 --

Nataly-Mak в сообщении #1026822 писал(а):
Имеем 16 различных чисел:

Код:
1, 2, 3, ..., 16

Надо сделать все возможные наборы по 4 различных числа.
Я посчитала, что их будет: число сочетаний из 16 по 4.

Ответом опять будет мультиномиальный коэффициент:$$\binom{16}{4,4,4,4}=\frac{16!}{4!\ 4!\ 4!\ 4!}=\frac{16!}{24^4}=63\ 063\ 000$$

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

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



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

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


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

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