Posts by Tomas Brada

61) Message boards : Science : Задача (Message 3753) Posted 29 May 2019 by Tomas Brada Post: Hi. I would like to point out that all these minimum and maximum CFs of groups will be found as a byproduct of the padls total search run in boinc project. None of the pivot points are necessary to perform the search. The search interval can be split at arbitrary points and re-adjusted dynamically depending on the run time. That's that. Can you please detail how are your methods of searching for minimum and maximum CF? And how are you searching in reverse? I really need to add checkpoint function to the program. I think I know how, we will see if it works.
62) Message boards : Science : О трансверсалях латинских квадратов (Message 3752) Posted 29 May 2019 by Tomas Brada Post: Thank you for bringing programs С. Беляева to my attention. I will read that too when I can sleep again. I have already read about Knuth's dancing links (DLX) in taocp pre-fascicle 4a.
63) Message boards : Science : О трансверсалях латинских квадратов (Message 3749) Posted 29 May 2019 by Tomas Brada Post: I wrote my last message to this thread without reading the thread first. The reason why I cited Vatutin, was because I read paper "Enumerating the Transversals for Diagonal Latin Squares of Small Order" first and learned about the terms there. I did not want to leave the claim without reference so I pasted the name. If i had read this thread, I would have cited this, or even your book. Also English paper was easier to read. Sorry for that. Now I understand more. And I see that the task 1 in my message is equivalent to finding all (CF) DLS, which there is a huge number of them. This is visible by writing the "set of disjoint pre-transversals" as a matrix of elements Vij (i=row, j=column), such that for transversal j, Vij is equal to column number of it's cell in row i. The matrix now has the same constraints as a LS. Yes, indeed, I re-invented a bicycle.
64) Message boards : Science : О трансверсалях латинских квадратов (Message 3694) Posted 22 May 2019 by Tomas Brada Post: Maybe this idea will lead somewhere, maybe not. For a DLK of order n to have orthogonal diagonal mate, it must posses a set of n disjoint diagonal transversals. Currently, first LK is generated and then checked for this property. Let's go the other way. First generate a set of disjoint diagonal pre-transversals and then fill the square with numbers such that it is DLK and pre-transversals are actual transversals. DKL constructed in such way is guaranteed to be ODLK. Two sub-problems are to be solved here: method to generate all sets of disjoint pre-transversals method to fill the square that satisfies conditions (row, column, diagonal and transversal) The second problem should be solvable by DLX. I am not sure about the first, but it can be enumerated. To determine whether this solution is feasible, the rough number of solutions to the fist problem must be estimated and then estimate how long it would take to check. Terms: DLK (diagonal latin square) matrix NxN of numbers 0..N-1 such that no number repeats in row, in column or in main diagonal, or in main anti-diagonal. Transversal: N-tuple of cells from LK such that no number repeats and on each row and on each column is one cell. Diagonal transversal: a transversal that contains one cell from each diagonal (can be same cell). (E.Vatutin team)
65) Message boards : Science : Алгоритм PADLS TOTAL (Message 3687) Posted 22 May 2019 by Tomas Brada Post: 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.
66) Message boards : Science : Алгоритм PADLS TOTAL (Message 3684) Posted 21 May 2019 by Tomas Brada Post: 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.
67) Message boards : Science : Алгоритм PADLS TOTAL (Message 3681) Posted 21 May 2019 by Tomas Brada Post: 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.
68) Message boards : Science : Алгоритм PADLS TOTAL (Message 3678) Posted 21 May 2019 by Tomas Brada Post: 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?
69) Message boards : Science : Алгоритм PADLS TOTAL (Message 3672) Posted 21 May 2019 by Tomas Brada Post: 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)?
70) Message boards : Science : Задача (Message 3671) Posted 21 May 2019 by Tomas Brada Post: Does this help? (line 51) 0 5 3 6 9 2 8 4 7 1 4 1 8 9 6 7 5 0 2 3 7 6 2 1 8 4 0 3 9 5 2 8 0 3 1 9 4 5 6 7 3 9 7 0 4 6 1 8 5 2 8 4 1 7 0 5 9 2 3 6 1 2 5 8 7 3 6 9 4 0 6 3 9 4 5 1 2 7 0 8 9 7 6 5 2 0 3 1 8 4 5 0 4 2 3 8 7 6 1 9
71) Message boards : Science : Алгоритм PADLS TOTAL (Message 3668) Posted 21 May 2019 by Tomas Brada Post: 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.
72) Message boards : Science : Задача (Message 3666) Posted 21 May 2019 by Tomas Brada Post: That is unforunate that both Harry While and Belyshev web site is not available. Should I write to Belyshev? On dxdy? I need the generator to do anything with it.
73) Message boards : Science : Алгоритм PADLS TOTAL (Message 3664) Posted 21 May 2019 by Tomas Brada Post: I ask for clarification. Are all CF DLS generated by generator_lk in lines 15, 38 and 51 pseudo associative? Is generator_lk THE generator for padls total? Why you want to use family_mar instead of the faster orthogonality test?
74) Message boards : Science : Задача (Message 3658) Posted 21 May 2019 by Tomas Brada Post: Since forum.boinc.ru is not accesible, do you have source to the Harry White's program (generator_lk)? I can not find it anywhere.
75) Message boards : Science : Алгоритм PADLS TOTAL (Message 3657) Posted 21 May 2019 by Tomas Brada Post: My initial attempt to remove izomorphs did remove the duplicates, but it also removed a lot of unique CF. Either it was just wrong approach, or it was due to use of weak generator. The CF transform could have moved the violations of associativity to other rows and so they appear as unique. But I am not sure. We will see how it works in the PADLS TOTAL. I of corse meant PADLS TOTAL, not Belysev's total in my previous message. Does PADLS TOTAL really generate only CF? Or how does it work.
76) Message boards : Science : Задача (Message 3655) Posted 21 May 2019 by Tomas Brada Post: Best strategy I can think of is to create program that would search SN DLS space from the highest LS down and check if KF(x)=x .
77) Message boards : Science : Задача (Message 3654) Posted 21 May 2019 by Tomas Brada Post: It seems so easy to find the maximum CF DLS in the row. But I have no idea how to do that. I had a look on the DLS canonization algorithm, but I do not understand how it works. It seems the enumeration of all CF DLS is the main problem EVatutin at. al. are trying to solve. (From that point, checking for ODLS is trivial.)
78) Message boards : Science : Алгоритм PADLS TOTAL (Message 3652) Posted 21 May 2019 by Tomas Brada Post: While you were writing I found a way to remove the isomorphs, but I must verify that is does not remove unique ones. I will check the other thread for how you solved the problem for TOTAL generator.
79) Message boards : Science : Алгоритм PADLS TOTAL (Message 3649) Posted 21 May 2019 by Tomas Brada Post: I just analysed ASS_DLK10A_R38 generator for workunit 2 3 4 5 7 8 9 6 and 2 3 4 5 7 9 8 6. There are 64 duplicate CF DLS. The duplicates are listed below in format 3 to save space. 2 3 4 5 7 8 9 6 produced 20960 CF DLS. 2 3 4 5 7 9 8 6 produced 23376 CF DLS, of which 64 are same as 2 3 4 5 7 8 9 6. Then I checked first (approx) 100 rows, and found 362152 duplicate CF DLS, which is 12.2% !!! LNmuvfrNnDVUX6DyF5Yi4eAK4 LNmuvjN8iDVUX6DyF5Yi4eA9q LNmuvkp2vSjnHfFf3DXKs6JTt LNmuvpKnrSjnHfFf3DXKs6Hsq LNmvDaCgiSPNFhiMuJJ8rerP3 LNmvDLZdLJG7WUGqD7VaQ5sWB LNmvDQHNSJG7WUGqD7VaQ5sL5 LNmvDRXHUSPNFhiMuJJ8rerZ9 LNmvkbSBBHhHqe5UYQXNXuEE6 LNmvkbSBB7ZoB5WFMHopdsJaW LNmvkeXxmHhHqe5UYQXNXuE5w LNmvkeXxm7ZoB5WFMHopdsJSM LNmvkgbpVHoSNqCEaS7xMusWr LNmvkgbpV5sSySat5Hdhcypgi LNmvkoDN1HoSNqCEaS7xMusAH LNmvkoDN15sSySat5HdhcypL9 LNmvniBhbHCXzUGyB1CQiwBFy LNmvniBhbSPNZpvGwJJ8nxafd LNmvniBhb1CSSVz4VHCWGuUAf LNmvnomKFHCXzUGyB1CQiwB7n LNmvnomKFSPNZpvGwJJ8nxaXS LNmvnomKF1CSSVz4VHCWGuU2U LNmvnoMLuHCXu9Yby1CQiwBgo LNmvnoMLuJG5eu2dm7VaLPcFu LNmvnoMLu1CSMBFhHHCWGuUbV LNmvnrT8VHCXu9Yby1CQiwBLC LNmvnrT8VJG5eu2dm7VaLPbuJ LNmvnrT8V1CSMBFhHHCWGuUEt LNmvSataNEVG7o8wP5tza5EeH LNmvSataNS8iydoEeEbAMX4ZT LNmvSfeFLEVG7o8wP5tza5EUC LNmvSfeFLS8iydoEeEbAMX4PN LNmvShW7tEXSSAquu7aaC3PrM LNmvShW7tQWc7UDatEWoiRnv1 LNmvSv7FQEXSSAquu7aaC3PgG LNmvSv7FQQWc7UDatEWoiRnjv LNmvVzNfTEzLMvQa61HQWtkPK LNmvVzNfTSjnbn3bfDXKoQ29P LNmvVzNfT1HS8V9rzEzJkL16R LNmvWMFDsDVSfWZoP5YhzwtnQ LNmvWMFDsEzLKUEXE1HQWtkXv LNmvWMFDs1HS62yp8EzJkL1F2 LNmvW6aEdDVSfWZoP5YhzwuVT LNmvW6aEdEzLKUEXE1HQWtmEy LNmvW6aEd1HS62yp8EzJkL1x5 LNmvW8r5XEzLMvQa61HQWtkKW LNmvW8r5XSjnbn3bfDXKoQ25a LNmvW8r5X1HS8V9rzEzJkL12c LNmv762UrHnxNQmmN7aXvU9yu LNmv762UrS6oTtuFSHW24N3gP LNmv762USHX3D7Y4tS7cms4aw LNmv762US7ZqHs3CpHops5hZD LNmv762UZHnxNQmmN7aXxZTc7 LNmv762UZS6oTtuFSHW26TMJb LNmv762U9HX3D7Y4tS7coxND9 LNmv762U97ZqHs3CpHopuB1BR LNmv766XzJkXUCAwiRm3Gtk6w LNmv766Xz6rYApDX8Jh2xo6PV LNmv766YKJkXUCAwiRm3ErkFV LNmv766YK6rYApDX8Jh2vm6Y3 LNmv766YXJgF5Nawc6ubREEif LNmv766YXRk8fYQ7aJiVGHm8P LNmv766Z8JgF5Nawc6ubLdT95 LNmv766Z8Rk8fYQ7aJiVBgyYo
80) Message boards : Science : Алгоритм PADLS TOTAL (Message 3645) Posted 21 May 2019 by Tomas Brada Post: Interesting. I subscribe. And I am still thinking how to remove duplicates to avoid repeated computations of the same data.

Previous 20 · Next 20