Are all CF DLS generated by generator_lk in lines 15, 38 and 51 pseudo associative?

Все СН ДЛК и все КФ СН ДЛК в линейках 15, 38 и 51 являются псевдоассоциативными, с разной степенью ассоциативности.

Is generator_lk THE generator for padls total?

Генератором для эксперимента PADLS TOTAL является генератор Белышева generator_kf.

Why you want to use family_mar instead of the faster orthogonality test?

Ах! Вы же сами ответили на этот вопрос :)

The family_mar program is more complex than checking whether a DLS is a ODLS. Checking that only requires enumerating the transversals and checking for a disjoint set thereof. Family_mar generates a whole family from that DLS and check them instead. So it is checking about 300 DLS instead of one DLS for othogonality.

https://boinc.progger.info/odlk/forum_thread.php?id=117&postid=3554#3554

Мой ответ здесь
https://boinc.progger.info/odlk/forum_thread.php?id=121&postid=3636#3636

Hurra! Now I understand this.
Then we must check that all the daughter squares that family_mar is checking are in ruler 15, 51 or 38 and that they do not repeat too much. BUT in padls total, all kf from these rows will be checked, so if the daughter square also belongs in the rulers, then it is not necessary to check them, because such will be checked later. And if the daughter square does not belong to the rulers, then they do not belong to the experiment.
From this thought, it seems the family_mar program is not needed here.

Then we must check that all the daughter squares that family_mar is checking are in ruler 15, 51 or 38 and that they do not repeat too much. BUT in padls total, all kf from these rows will be checked, so if the daughter square also belongs in the rulers, then it is not necessary to check them, because such will be checked later. And if the daughter square does not belong to the rulers, then they do not belong to the experiment.
From this thought, it seems the family_mar program is not needed here.

Я ничего не поняла тут.

Мы берём линейку №51 и генерируем в этой линейке КФ СН ДЛК.
Все эти КФ являются псевдоассоциативными ДЛК и все они различные.
Если мы применим к этим КФ только поиск ортогональных им ДЛК (что, кстати, делается в проекте ODLK), мы найдём тысячную долю решений (примерно).
Проверка должна выполняться программой family_mar!
Я уже тестирую этот эксперимент и получаю уникальные решения от тех КФ линейки №51, которые не имеют ортогональных ДЛК.

Пожалуйста, прочтите ещё раз внимательно эту ветку, а также ветку "Задача".
Мне приходится разъяснять одно и то же несколько раз.

By reading the Family_mar program, I understand it works as follows:
From each input LS, many more squares are derived. Let's call those daughter squares. And then, each daughter square is checked for orthogonality. The program works so fast, because a expensive step of transversal enumeration is performed only once for each input square and is shared for all the daughter squares. There are average of 300 daughter squares per input square. I do not yet understand how these are generated.
Do you understand?
Now what these daughter squares look like? I picked a bad example, because it has 509 daughter squares. I only show some.
The example square has 868 trasversals, of which 131 are "diagonal".

Input Square:
MFU8P9W4nERBJRxCqKoiBbzmz #lin=39 (line №39)
Daughter squares:
7TBNWSbTrQcULyGBq3KkYgEYV #lin=12
GsByHUmwv4qZ1u1PUNeXjwxvu #lin=30
MQ8aQpTyGSVs1JhSoGZVfschW #lin=39
ACHesZJxXJvnsXCrM4U98KzUC #lin=17
XdRoZYnGhJg7Y2Sq787xHNNof #lin=59
7ekgqDzZjGd9yCcvv39RJXjHg #lin=12
BzeVDKEbDGihTmcGHRbrT9kmv #lin=21
SbK5grSkSDtie77Mj11HHTcw9 #lin=49
FhEBGcVuL19ZMbA9dQMRqBi3q #lin=28
NHyQ5Zjn972k9zgDy26NoeCGF #lin=41
. . .
MFU8P9W4nERBJRxCqKoiBbzmz #lin=39
1HgEzStK3DU6M3E5RAgpYTPFx #lin=0
8Q7a3F4iGJNjyvDkwBAZzPxRX #lin=14
8Q7a3EzDZJNjyv36FBAa9NiU1 #lin=14
Tu9z184RgCnfNcq2pS5fEhbxS #lin=52
2JnoY54D8LJSLjJn3AwyLoAkT #lin=2
CBn5b8jKg66isELKhCSZ4LcGv #lin=21
3zKxLwgGk2NyYq9n7CoEpU6WV #lin=5
 . . .

See - a lot of different line numbers. 13 of them are from line number 39, others are from bunch of other lines.
These 13 (12 without original) will become duplicate, as they will be checked in other workunits.
What about the other lines? Can they be orthogonal? Should they be checked? Should the be part of the results (if orthogonal)?

---

Из какой линейки вы взяли исходную КФ СН ДЛК для проверки программой family_mar?
Что у вас означает lin=39, lin=21 и т. д.?

Я понимаю, как работает программа family_mar только в общей идее, но не в деталях.
За разъяснением деталей работы этой программы, пожалуйста, обратитесь к автору программы.

Input Square:
MFU8P9W4nERBJRxCqKoiBbzmz #lin=39 (line №39)

Вы хотите сказать, что исходный квадрат из линейки №39?

Этот квадрат:

MFU8P9W4nERBJRxCqKoiBbzmz

0 2 3 7 8 9 5 6 4 1
3 1 8 5 0 7 9 4 2 6
8 5 2 6 3 1 7 0 9 4
2 7 1 3 9 8 4 5 6 0
1 8 0 9 4 6 3 2 5 7
6 9 4 0 7 5 2 8 1 3
7 0 5 8 1 4 6 9 3 2
4 6 9 2 5 3 1 7 0 8
9 3 7 4 6 2 0 1 8 5
5 4 6 1 2 0 8 3 7 9

не принадлежит линейке №39.
В линейке №39 побочная диагональ СН ДЛК имеет вид

1 2 0 4 6 3 7 9 5 8

It seems I made a mistake with the rule number. Is this rule 1,0,3,2,6,7,4,5,9,8 - number 0 or number 1?

Побочные диагонали линеек по теории Белышева

№1 1032674598 
№2 1032674895 
№3 1032675498 
№4 1032678945 
№5 1032678954 
№6 1032684957 
№7 1032684975 
№8 1032685947 
№9 1032685974 
№10 1032687495 
№11 1032689475 
№12 1032689574 
№13 1034268957 
№14 1034268975 
№15 1034275698 
№16 1034275896 
№17 1034278956 
№18 1034278965 
№19 1034625897
№20 1034628597 
№21 1034628957 
№22 1034682975 
№23 1034685927 
№24 1034687925 
№25 1034687952 
№26 1034728956 
№27 1034728965 
№28 1034785926 
№29 1034785962 
№30 1034875926 
№31 1034875962 
№32 1034895627 
№33 1034895672 
№34 1037685924 
№35 1037685942 
№36 1037892645 
№37 1037892654 
№38 1204635978 
№39 1204637958 
№40 1204678935 
№41 1204785936 
№42 1204785963 
№43 1204789365 
№44 1204789563 
№45 1204798536 
№46 1204798653 
№47 1230678954 
№48 1230679458 
№49 1234075968 
№50 1234078956 
№51 1234095678 
№52 1234608975 
№53 1234675908 
№54 1234689507 
№55 1237685904 
№56 1237695408 
№57 1032675894 
№58 1034628975 
№59 1034678925 
№60 1034678952 
№61 1034685972 
№62 1034689527 
№63 1034689572 
№64 1034869527 
№65 1204678953 
№66 1230675948 
№67 1234698057 

А знаете ли вы, почему линеек 67? :)
Белышев сделал гениальное открытие линеек в 2017 году; было мне в ту пору 67 лет :)
Разумеется, это шутка. Просто совпадение такое.

So it is that my program reports rule number one less. I correct the program. In my message (2672), the lin means rule number. In the code from Белышев, it is called "lin", but it is one less. So #lin=39 is rule №40. Silly mistake. But this fact does not change the idea.

Tomas Brada
неважно, что вы ошиблись в нумерации линеек.
Ну вот, программа family_mar нашла много ДЛК, разумеется, они из каких-то линеек.
И что из этого?
Все эти ДЛК должны быть проверены на наличие у них ОДЛК; проверены сейчас, а не тогда, когда будут проверяться соответствующие линейки.

But this fact does not change the idea.

Да, я вам уже ответила.
В этом факте нет никакой идеи.
Идея в том, что эти ДЛК из разных линеек нужно проверить сейчас на ОДЛК и найти все решения.
Линейка №21 (и другие линейки), может быть, будет проверяться через 10 лет.
Я могу не успеть :)

Например, найденные мной уникальные решения при тестировании эксперимента PADLS TOTAL rule 51

0 4 5 9 3 2 7 8 6 1
4 1 6 0 8 3 5 9 2 7
5 7 2 1 0 8 9 3 4 6
6 8 7 3 2 9 4 1 0 5
1 3 9 7 4 6 8 2 5 0
8 0 1 4 9 5 2 6 7 3
2 9 3 8 7 0 6 5 1 4
3 2 0 5 6 4 1 7 9 8
9 5 4 6 1 7 3 0 8 2
7 6 8 2 5 1 0 4 3 9

0 4 6 7 2 9 8 5 3 1
6 1 7 8 3 4 0 9 2 5
8 5 2 9 0 1 4 3 7 6
5 2 4 3 1 8 7 6 9 0
7 9 5 1 4 6 2 8 0 3
3 7 0 4 8 5 9 1 6 2
9 8 3 5 7 2 6 0 1 4
1 6 9 2 5 0 3 7 4 8
2 0 1 6 9 3 5 4 8 7
4 3 8 0 6 7 1 2 5 9

0 2 4 8 9 3 7 6 5 1
4 1 7 5 0 6 8 9 2 3
8 7 2 4 3 1 5 0 9 6
1 8 9 3 6 2 4 5 7 0
2 9 0 6 4 7 1 8 3 5
7 4 6 0 8 5 9 3 1 2
5 3 1 9 7 8 6 2 0 4
6 0 5 1 2 9 3 7 4 8
9 6 3 2 5 4 0 1 8 7
3 5 8 7 1 0 2 4 6 9

0 5 3 2 9 7 8 4 6 1
7 1 8 4 5 9 2 6 0 3
5 9 2 8 1 0 4 3 7 6
9 8 6 3 2 1 7 0 5 4
8 7 1 0 4 6 3 5 9 2
3 2 7 6 8 5 9 1 4 0
1 0 4 5 7 2 6 9 3 8
4 6 9 1 3 8 0 7 2 5
6 4 5 9 0 3 1 2 8 7
2 3 0 7 6 4 5 8 1 9

0 6 7 8 3 9 5 2 4 1
3 1 5 7 0 8 9 4 2 6
4 9 2 1 5 0 7 3 6 8
2 5 8 3 1 4 0 6 9 7
1 0 3 9 4 6 8 5 7 2
9 3 6 4 7 5 2 8 1 0
7 2 4 5 8 1 6 9 0 3
5 8 9 0 6 2 1 7 3 4
6 4 0 2 9 7 3 1 8 5
8 7 1 6 2 3 4 0 5 9

Все они из каких-то линеек.

Great! Now I have answer to my question.
> What about the other rules? Can they be orthogonal? Should they be checked? Should the be part of the results (if orthogonal)?
Yes, we also include the other lines.
This is very interesting. Still the rule numbers of daughter squares can be used to eliminate some double checking.

Still the rule numbers of daughter squares can be used to eliminate some double checking.

Если вас так пугает "двойная проверка", не надо ничего проверять :)
Установление номеров линеек всех ДЛК (получаемых в процессе работы программы family_mar) и выяснение вопроса, были ли эти ДЛК уже проверены раньше, займёт больше времени, чем их "двойная проверка".

Сейчас выполняются эксперименты PADLS rule 15 и PADLS rule 51, в которых очень много повторных проверок.
Но мы получаем также уникальные решения за счёт нового генератора 2.
Я выполняю эксперимент PADLS генератор 4, rule 38, в котором тоже много повторных проверок.
Но я получаю и уникальные решения! Эти решения не были получены ни при первом выполнении эксперимента PADLS rule 38 мной и Demis в ручном режиме, ни при втором выполнении этого эксперимента в вашем BOINC-проекте.
Я показала примеры таких решений
https://boinc.progger.info/odlk/forum_thread.php?id=107&postid=3631#3631

Предлагаю вам разработать свой алгоритм, в котором совсем не будет "двойных проверок" и запустить его в BOINC-проекте.

Yes, I know that checking for duplicate work is work in itself. Such check must be fast, otherwiese it is not worth it. The rule numbers are already calculated as a byproduct in the program! We will see.

The rule numbers are already calculated as a byproduct in the program

Хорошо, допустим, что номера линеек в программе family_mar уже определены.
Но как вы установите по всем линейкам, были ли проверены данные ДЛК из этих линеек?
Вероятность того, что они были проверены, ничтожно мала.
Линейки содержат огромное количество СН ДЛК и КФ СН ДЛК!
Такая проверка потребует немало времени.
Гораздо быстрее сразу проверить все ДЛК на ОДЛК.
Это моё мнение.

Желаю вам удачи в вашем алгоритме без "двойных проверок".
Я предпочитаю свой вариант алгоритма.
В алгоритме PADLS TOTAL работают всего две программы Белышева: generator_kf и family_mar.
Обе программы многократно опробованы и работают отлично.
Я ничего не буду изменять в своём алгоритме.
Если вы хотите запустить мой алгоритм без изменений, пожалуйста.
Если вы хотите изменить мой алгоритм, тоже пожалуйста, но тогда это будет уже ваш алгоритм.
Вы запускаете его в BOINC-проекте сами, без моего участия.

Цитата (из темы "Задача")

Ну, если не вся линейка №51 может быть взята в разработку, то половина её точно может быть взята.
Это 1 - 3102 группы. В 3102 группе у меня есть и текущий максимум КФ.
В 1-ой группе есть минимальная КФ.
Всё - границы заданы чётко и однозначно.
Перечисляем все КФ в этих границах (как верно заметил Tomas Brada, это самая сложная часть задачи) и проверяем их.
Проверять КФ можно двумя способами:

1. Просто проверка на наличие у КФ ортрогональных ДЛК.
Эта проверка уже выполняется в BOINC-проекте ODLK для линейки №51.

2. Проверка КФ программой Белышева family_mar.
Смотрим на КФ, как на псевдоассоциативные ДЛК.
Это алгоритм PADLS TOTAL.

Совершенно понятно, что первая проверка потребует намного меньше времени, чем вторая проверка.
Но и решений при первой проверке найдётся в разы меньше!

Итак, берём линейку №51 в полную разработку?
Кто смелый? :)
Ну, для начала хотя бы половину линейки или даже третью часть. Третья часть - это всего 2068 групп.

Ещё раз подчеркну: главная сложность алгоритма PADLS TOTAL - генерация КФ. Проверка программой Белышева family_mar выполняется стандартно и уверенно, многократно это опробовано.

https://boinc.progger.info/odlk/forum_thread.php?id=115&postid=3701#3701

Цитата

Замечание 5.
Очень важный момент: проверка программой family_mar найдёт все решения: и те, что получаются непосредственно от ДЛК линеек 15, 38, 51 проверкой их на наличие ортогональных ДЛК, и те, что получаются только сложной проверкой алгоритмом, реализованным в программе family_mar.

Продемонстрирую это замечание на примере.

Вот интервал между двумя КФ ОДЛК, решения взяты с проекта ODLK

КФ ОДЛК1
0 2 3 4 5 6 7 8 9 1
3 1 0 6 7 4 9 5 2 8
7 5 2 1 0 9 8 3 6 4
6 9 5 3 1 8 4 2 0 7
9 6 8 7 4 0 2 1 5 3
2 4 1 8 9 5 3 0 7 6
4 0 7 5 8 1 6 9 3 2
5 8 6 9 3 2 1 7 4 0
1 7 9 2 6 3 0 4 8 5
8 3 4 0 2 7 5 6 1 9

КФ ОДЛК2
0 2 3 4 5 6 7 8 9 1
3 1 0 6 7 4 9 5 2 8
7 5 2 1 0 9 8 3 6 4
6 9 8 3 2 1 4 0 5 7
2 3 5 8 4 0 1 9 7 6
4 8 1 7 9 5 0 6 3 2
9 0 7 5 1 8 6 2 4 3
5 4 6 9 8 3 2 7 1 0
1 7 9 0 6 2 3 4 8 5
8 6 4 2 3 7 5 1 0 9

Определяем, сколько в этом интервале имеется КФ. Это делается с помощью программы Белышева moschnometr_kf.
Смотрите об этой программе тему
https://boinc.progger.info/odlk/forum_thread.php?id=27#398

Итак, определили, что в данном интервале

Найдено СНДЛК:  824102
Найдено КФ:     824102

Очень хорошо!
Теперь генерируем 824102 КФ программой generator_kf и проверяем их программой family_mar.
[Замечу, что КФ генерируются, начиная со следующей за КФ ОДЛК1 КФ, и до конца интервала, то есть включая КФ ОДЛК2.]
Найдено 9 решений, в том числе КФ ОДЛК2.

Если вы проверите все 824102 КФ интервала на наличие у них ортогональных ДЛК, будет найдено всего одно решение - КФ ОДЛК2!!!

Вот так всё просто! Ну очень просто!
Я проверила уже десятки интервалов. Во всех интервалах решения найдены, и все уникальные.
Конечно, я выбрала лёгкие (короткие) интервалы, в которых не больше миллиона КФ.
Есть огромные интервалы, содержащие несколько миллионов КФ.

Товарищи! Господа!
Ну где вы с кластерами и суперкомпьютерами??? :)

Задаёте минимальную КФ, задаёте максимальную КФ, запускаете генератор КФ (программа Белышева generator_kf), программа генерирует КФ, хватаете их и отправляете на проверку программой Белышева family_mar.
Всё!
Сколько времени потребуется суперкомпьютеру для решения этой задачи?
Думаю, может быть, за месяц управится :) Это если половину линейки №51 взять в обработку.
BOINC-проект уровня ODLK1, возможно, справится за год - полтора - два.
Один ПК моего уровня не справится и за 10 лет.

Минимальная КФ



Максимальная КФ

0 5 4 7 8 6 9 2 3 1
9 1 8 4 7 3 0 6 2 5
5 4 2 6 0 8 1 3 9 7
1 2 9 3 5 7 4 8 0 6
6 8 5 2 4 0 7 9 1 3
7 3 0 1 9 5 8 4 6 2
3 9 1 5 2 4 6 0 7 8
2 0 6 8 1 9 3 7 5 4
4 7 3 9 6 2 5 1 8 0
8 6 7 0 3 1 2 5 4 9

И две программы Белышева. И больше ничего не надо!
И всё решается сразу и до конца.

Покажите же миру свою мощную технику!
Что она может на самом деле.
А то только разговоры слышу: кластеры, суперкомпьютеры...
А где они? Не видно что-то.

PS. Замечу, что в BOINC-проекте ODLK линейка №51 проверяется более лёгкой проверкой (только на наличие ОДЛК у КФ); проверяется уже больше года; половина линейки ещё не проверена.

А посмотрите-ка на максимальную КФ (которую я имею в линейке №51 на данный момент)



Весьма интересный псевдоассоциативный ДЛК!

Повторю основной тезис: все СН ДЛК и КФ СН ДЛК в линейках 15, 38 и 51 являются псевдоассоциативными ДЛК с разной степенью ассоциативности.
Сравните степень ассоциативности в минимальной КФ (см. предыдущий пост) и в максимальной КФ (нарушения ассоциативности в обеих КФ в белых ячейках).

Накапливаю банк КФ в линейке №51 для эксперимента PADLS TOTAL.
Зачем нужен банк КФ? Это опорные точки - границы интервалов.
Зачем нужны интервалы?
Интервалы нужны для возможности делать генерацию КФ порционной.
Понятно же, что в заданном интервале КФ гораздо проще сгенерировать.

Как уже отмечалось выше, в линейке №51 есть очень проблемные для генерации КФ области, в которых на миллиарды СН ДЛК нет ни одной КФ.
Вот для таких областей необходимы опорные точки, которые задают интервалы.

В начале линейки всё просто.
Например, самый первый интервал

минимальная КФ
0 2 3 4 5 6 7 8 9 1
3 1 0 6 7 4 5 9 2 8
1 0 2 7 6 8 9 3 4 5
2 5 1 3 8 9 4 0 6 7
5 3 7 9 4 0 8 2 1 6
6 4 8 0 9 5 2 1 7 3
7 8 9 5 0 1 6 4 3 2
4 9 6 8 1 2 3 7 5 0
9 7 5 1 2 3 0 6 8 4
8 6 4 2 3 7 1 5 0 9

минимальная КФ ОДЛК
0 2 3 4 5 6 7 8 9 1
3 1 0 6 7 4 5 9 2 8
1 0 2 9 6 7 8 3 4 5
7 6 9 3 8 1 4 5 0 2
9 5 8 1 4 0 3 2 6 7
6 3 1 8 9 5 2 4 7 0
2 9 7 5 1 8 6 0 3 4
4 8 6 0 2 9 1 7 5 3
5 7 4 2 0 3 9 1 8 6
8 4 5 7 3 2 0 6 1 9

В этом интервале программой Белышева moschnometr_kf

Найдено СНДЛК:  93562426
Найдено КФ:     93562426

Больше 93 миллионов СН ДЛК и все они КФ!
Понятно, что тут нет проблем с генерацией КФ.

Кстати, я уже давно проверяю этот интервал в эксперименте PADLS TOTAL.
Решения идут стабильно и все пока уникальные.
Проверила 11 миллионов КФ в данном интервале.