Метод точных попарно ортогональных покрытий массива

[Nataly-Mak]

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

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

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

[Nataly-Mak]

А теперь разделим так перве 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? И исчерпаются ли этим все варианты наборов цепочек??

[DanilovV]

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

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

[Nataly-Mak]

DanilovV в сообщении #1026780 писал(а):

Цепочку

89  101  113  131  1361 2591  2609  2621  2633

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

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

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

[DanilovV]

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

[Nataly-Mak]

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

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

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

[DanilovV]

Nataly-Mak в сообщении #1026785 писал(а):

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

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

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

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

[Nataly-Mak]

DanilovV в сообщении #1026790 писал(а):

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

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

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

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

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

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

[DanilovV]

Nataly-Mak в сообщении #1026793 писал(а):

DanilovV в сообщении #1026790 писал(а):

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

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

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

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

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

[Nataly-Mak]

DanilovV в сообщении #1026794 писал(а):

И как будет проверятся программа, если в ней где-то вкралась ошибка?

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

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

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

62852101650
40!/24!/(24)^4=3963642086353950000

Кто больше?

-- Сб июн 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-х цепочек.

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

[DanilovV]

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 

[Nataly-Mak]

Цитата:

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

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

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

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

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

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

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

[DanilovV]

Nataly-Mak в сообщении #1026810 писал(а):

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

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

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

[Nataly-Mak]

DanilovV в сообщении #1026816 писал(а):

Откуда взялось 1820?

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

1, 2, 3, ..., 16

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

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

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

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

[whitefox]

Nataly-Mak в сообщении #1026797 писал(а):

Есть уже два варианта ответа на вопрос:

62852101650
40!/24!/(24)^4=3963642086353950000

Кто больше?

Ответом будет мультиномиальный коэффициент:

$$\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$$