Minlex Form: Min and Max Lists / Chaining

Programs which generate, solve, and analyze Sudoku puzzles

Minlex Form: Min and Max Lists / Chaining

Postby holdout » Sun Jul 31, 2011 10:07 pm

My recent work on converting solution grids to minlex form has allowed me to find other minlex forms that are in the extreme neighborhoods. The known minimum and maximum forms have been taken from a post by daj95376. The lists are my own.

If you are interested in converting full solution grids to minlex form in a very fast way, then download "Minlex Form and Chaining.docx" (attached to bottom of this post). Timing tests show that solution grids can be converted at a rate of just over 50,000 per second on a 2.33 Ghz computer.

Also attached is file "MinlexForm-2.c", containing 'C' code to transform solution grids to minlex form.
Attachments
MinlexForm-2.c
MinlexForm-2.c
(24.94 KiB) Downloaded 449 times
Minlex Form and Chaining.docx
Minlex Form and Chaining
(27.75 KiB) Downloaded 515 times
Last edited by holdout on Thu May 16, 2013 7:57 pm, edited 4 times in total.
holdout
 
Posts: 35
Joined: 30 August 2005
Location: Bowie, Maryland USA

Re: Minlex Form: Min and Max Lists

Postby Serg » Wed Aug 03, 2011 10:03 am

Hi, holdout!
Would you post the link to discussion cited by you? (Unfortunately I don't understand some terms ("row rank", etc.).)

Serg
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Minlex Form: Min and Max Lists

Postby holdout » Wed Aug 03, 2011 1:11 pm

Serg wrote:
Would you post the link to discussion cited by you? (Unfortunately I don't understand some terms ("row rank", etc.).)


I have edited the original post (at the top). The link to post is much clearer now. Go to the indicated post and open the attached ".docx" document.
holdout
 
Posts: 35
Joined: 30 August 2005
Location: Bowie, Maryland USA

Re: Minlex Form: Min and Max Lists

Postby Serg » Sat Aug 06, 2011 8:50 pm

Hi, holdout!
I've studied your article. You've done very intersting observation! But what about proof of your discovery - that cycle standard form and row rank have one-to-one correspondence. Do you have such proof?

If my understanding is right, number of minlex forms is the same as number of essentially different solution grids (about 5 billions). So, all solution grids can be devided by 14 classes based on minimal row ranks. Can it be analysed by apparatus of Group Theory?

About minimal and maximal list posted by you. Very interesting data. I am not sure my undertanding is correct. I think you considered 6+6+6=18 two-rows combination (two rows were selected always from the same band) and 6+6+6=18 two-columns combinations (two rows were selected always from the same chute). You calculated 36 "row 2 ranks" - one for each combination. Then you selected minimal row rank (for minimal list) and maximal row rank (for maximal list). Is it right?

Serg
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Minlex Form: Min and Max Lists

Postby holdout » Sun Aug 07, 2011 11:39 pm

Dear Serg,

1. You ask if I have proof that cycle standard form and row rank are in one-to-one correspondence.
--- Yes, if you accept the results of the following experiment.

After setting row-1 to '123456789', I looped over all 12096 (= 56 x 6 x 6 x 6) choices for row-2.
I converted each row pair to: A) two-row minlex form, and B) cycle standard form.
Both (A) and (B) were output on the same line.
Lines were sorted, duplicates removed, and counted.
There were exactly 15 lines in the final output file, proving a 1 - 1 correspondence.

2. You ask if the number of minlex forms is the same as number of essentially different solution grids.
--- Yes, that is correct.

3. You ask if all solution grids can be devided into 14 classes based on minimal row ranks.
--- Yes, that is correct, since there are no solution grids with with minimal row rank = 15.

4. You ask this phenomenon can be analysed by apparatus of Group Theory.
--- I do not know.

Let me say a few words about how the lists were generated.
Suppose we want to construct all solution grids which have minimum row rank = 11.
a) Of course, row-1 is '123456789' and row-2 is '457289631'.
b) Next, try all Soduko-legal choices for row-3.
Find the rank of row-1 vs. row-3 and the rank of row-2 vs. row-3.
If either rank is less than 11, then row-3 is not a good choice (try again).
c) Now that band-1 is full, let's loop over choices for the remainder of column-1.
In every minlex grid, row-4, column-1 is always '2'. That is, r4[1] = 2.
Also, we know that r4[1] < r5[1] < r6[1] and r7[1] < r8[1] < r9[1] and r4[1] < r7[1].
This is a lot of restrictions (there are only 10 ways to fill the remainder of column-1).
d) Next, loop over the legal choices for the remainder of column-2.
By treating column-1 and column-2 as rows, we can find their row rank.
Again, if the rank is less than 11, we have made a bad choice (try again).
e) Next, loop ove the legal choices for the remainder of column-3.
Find the rank of column-1 vs. column-3 and column-2 vs. column-3.
If either rank is less than 11, then column-3 is not a good choice (try again).
f) The rest of the procedure follows the same basic outline.

After the grid is full, we can say that the grid has minimum rank 11, because each time we have
added a row (or column), we checked. (There are 18 checks.)

The grids generated by this procedure are not in minlex form, so for each grid that pops out we need to convert it minlex form. All minlex forms are saved. Later, duplicates are removed. This is all quite fast and takes only a few minutes to execute.

The algorithm is rerun, but with the insistance that the minimum rank be 12. Then 13. Then 14.

Suppose we want to construct all solution grids which have maximum row rank = 3.
The procedure is very similar, but with a different starting point for row-2.
Also, the condition changes from "at least rank = 11" to "at most rank = 3".

Your questions were pretty good,
Holdout
holdout
 
Posts: 35
Joined: 30 August 2005
Location: Bowie, Maryland USA

Re: Minlex Form: Min and Max Lists

Postby Serg » Tue Aug 09, 2011 12:56 pm

Hello, holdout!
Thank you for clarification. I understood your answer (it is very transparent and clear). I feel Group Theory could be useful for minlex forms analysis. Maybe I'll propose smth (I am not sure I can do it).

Thanks, Serg.
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Minlex Form: Min and Max Lists

Postby dobrichev » Wed Aug 10, 2011 8:15 pm

Hello holdout,

I finally read your article. The "x" in the file extension caused some problems :x

As far as I understand, your approach is to score the row pairs, eliminating all but the best candidates for further processing.

Congratulations, this could really improve the speed of grid normalization in significant degree.

In Table A there is a column for #Ways to obtain the same result by different permutations and relabeling. It is automorphism level. Several permutations result to indistinguishable results, but this is true only in the context of these two rows.
Do you take into account that for the third row (and later for the next 2 bands) you must check all these ways?
Also we don't know the order of the first two rows, which should double the #Ways when the goal is normalization of the complete grid. Am I right?

From other point of view, it is known that there are exactly 416 essentially different bands, and you group them into 14 classes. It is interesting whether some of these "row pair" classes will dominate in some types of grids - these with low-clue or high-clue puzzles, with high degree of symmetry, etc.

A fast normalization algorithm could be useful for generation of all essentially different grids. Currently, if somebody wants to perform some operation over all grids, he/she must use large catalog in compressed or uncompressed form. I am using a catalog compressed to 54GB, and decompression itself takes ~2 hours. If there is a tool, capable to produce a stream of all grids with same or better speed, it will be helpful.

Finally, some words about the ideal normalization algorithm.
It must be capable to perform the operation in 2 steps: obtain the "transformation(s)", then apply the transformation(s) to the given grid or to a subgrid (puzzle). For grids with automorphism level > 1 there must be a list of valid transformations, up to 648.
It must be capable to perform reverse transformations.
It must be thread-safe, which is not the case in gsf's implementation of your puzzle minlex algorithm (the static buffer for the stacks).

I like the "undocumented feature" of your algorithm to normalize invalid puzzles. Replacing all givens by "1" transforms any template to its minlex form very well. If you are planning to open your improved code, I'll be happy if you keep this feature.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: Minlex Form: Min and Max Lists

Postby holdout » Thu Aug 11, 2011 3:01 pm

Dear Mladen Dobrichev,

I'm sorry that the ".docx" file type, a Microsoft creation, has caused a few problems.

A few years ago I wrote a 'C++' program to convert both partial and full Soduko grids to minlex form. About three months ago, to my chagrin and edification, you brought to my attention a logic error in the part of the code that deals with partial grids. I decided to re-write the whole thing. In doing so, I re-visited the full grid problem.

Let me address questions dealing with converting full solution grids to minlex form.

1. Yes, my approach is to score row pairs, saving only the best for futher processing.
First, compute the puzzle transpose, so that chutes can be treated as three extra bands.
Next, compute the "rank" of each pair of rows within a band. Since the rank of row-x vs. row-y is the same as row-y vs. row-x, only 18 routine calls need be made. Only row pairs of lowest rank need be considered as candidates for the first two rows in the minlex matrix.

2. If row-x and row-y are one of the candidate pairs, either order could be correct, and both choices must be pursued.

3. Suppose we wish to pursue row-x vs. row-y. Since we know the rank of row-x vs. row-y, we also know:
a) exactly what row-1 and row-2 of the minlex matrix will be. (Our goal.)
b) the "#Ways" that row-x/row-y can be transformed into our goal.
c) the cycle structure of our goal and the cycle structure of row-x/row-y.
d) how to quickly generate a dual key set for row-y vs. row-x using a known permutation.

There is a way (not detailed in the reference, because of complexity) to generate a set of keys which transform row-x/row-y to our goal. Although row-y/row-x keys could be generated using the same scheme, it is much faster to generate the dual key set from the one we already have, using a known permutation.

4. We are really flying now. Row-1 and row-2 are filled. We know the entire 9-long "column" key and the substututions needed to make row-1 equal to '123456789'. So we just plop-in row-3 with the only remaining row from the xy-band and "score". The "score" is whatever row-3 turns out to be. At this point, the number of competing answers will usually be reduced to just one.

5. To order minlex rows 4 thru 9, we need only to examine the translated (substituted) digits in the first column in the rows of the two bands we have not already used (we should know whether we are dealing with the original or its transpose).

Here follows some of your statements/questions and my comments.

*** In Table A there is a column for #Ways to obtain the same result by different permutations and relabeling. It is automorphism level. Several permutations result to indistinguishable results, but this is true only in the context of these two rows.

--- Sorry, I don't understand the question.

*** Do you take into account that for the third row (and later for the next 2 bands) you must check all these ways?

--- After the initial 18 "checks", no further checks are made. The computation of "rank" is just to quickly find candidates for minlex row-1 and row-2.

*** From other point of view, it is known that there are exactly 416 essentially different bands, and you group them into 14 classes.

--- When I was generating the min and max lists, I really didn't consider that grids could also be classified by minimum or maximum rank, though what you say is true. I just wanted to see if I could do it.

*** A fast normalization algorithm could be useful for generation of all essentially different grids.

--- The algorithm I used to normalize full grids is certainly fast, but it may not be fast enough for your proposed applications.

*** Finally, some words about the ideal normalization algorithm. It must be capable to perform the operation in 2 steps: obtain the "transformation(s)", then apply the transformation(s) to the given grid or to a subgrid (puzzle). For grids with automorphism level > 1 there must be a list of valid transformations, up to 648. It must be capable to perform reverse transformations. It must be thread-safe, which is not the case in gsf's implementation of your puzzle minlex algorithm (the static buffer for the stacks).

--- I do not know the meaning of: 1) "automorphism level > 1" or 2) "reverse transformation" or 3) "thread-safe".
Your mentioned a "list of valid transformations, up to 648". I stated earlier that after row-3 is added to the minlex matrix that the number of competing answers will usually be reduced to just one. In one very special case, the number of competing answers is 648, and that is when the the first three rows of the minlex matrix are:
Code: Select all
123 456 789
456 789 123
789 123 456


--- The updated version of the routine will be in 'C', and the normalization of partial puzzles will be about the same, hopefully without the logic bug. I will email to you some 'C' code showing how I compute "rank".

Cheers,
holdout
holdout
 
Posts: 35
Joined: 30 August 2005
Location: Bowie, Maryland USA

Re: Minlex Form: Min and Max Lists

Postby dobrichev » Thu Aug 11, 2011 8:17 pm

Hi holdout,

Thank you for the detailed answers.

holdout wrote:*** In Table A there is a column for #Ways to obtain the same result by different permutations and relabeling. It is automorphism level. Several permutations result to indistinguishable results, but this is true only in the context of these two rows.

--- Sorry, I don't understand the question.

*** Do you take into account that for the third row (and later for the next 2 bands) you must check all these ways?

--- After the initial 18 "checks", no further checks are made. The computation of "rank" is just to quickly find candidates for minlex row-1 and row-2.

Your answer to the second question above, along with these remarks
2. If row-x and row-y are one of the candidate pairs, either order could be correct, and both choices must be pursued.
...
we also know ... b) the "#Ways" that row-x/row-y can be transformed into our goal.

answers also the first question. Yes, it was not a question but a warning after fixing first two rows not to forget to loop over all possible transformations instead of choosing a random one.


holdout wrote:*** Finally, some words about the ideal normalization algorithm. It must be capable to perform the operation in 2 steps: obtain the "transformation(s)", then apply the transformation(s) to the given grid or to a subgrid (puzzle). For grids with automorphism level > 1 there must be a list of valid transformations, up to 648. It must be capable to perform reverse transformations. It must be thread-safe, which is not the case in gsf's implementation of your puzzle minlex algorithm (the static buffer for the stacks).

--- I do not know the meaning of: 1) "automorphism level > 1" or 2) "reverse transformation" or 3) "thread-safe".


Automorphism.
See Automorphic Sudokus, How to calculate number of pattern's automorphisms?. This is the distribution of grids by level of automorphism, initially published by gsf (sorry but I lost the link to the original post).
Code: Select all
1   5472170387
2   548449
3   7336
4   2826
6   1257
8   29
9   42
12   92
18   85
27   2
36   15
54   11
72   2
108   3
162   1
648   1

For each of the 5472170387 grids there is exactly one transformation which, applied to a chosen isomorph of the respective grid, uniquely transforms it to the predefined canonical form (say row-minlex form). For the rest, there is more than one valid transformation. Transformed grids are indistinguishable, but transformed puzzles might be distinguishable.

Reversed transformation.
Suppose we have 2 grids which differ only in the permutations of values within a unavoidable rectangle. It is expected that both solution grids
a) are not necessarily close to each other when represented in minlex form;
b) are very close in most of their properties.
Suppose we have 2 sets of puzzles, each solved to some isomorph of one of the grids.
Transforming each solution to minlex form, then applying the same transformation to the puzzle, will give comparable puzzles for each of the grids.
But how to compare the puzzles from one set to other? One possible way is, knowing the representations of the solution grids which are close (differ in only 4 cell values), to canonicalize them (along with puzzles), then to apply the "reverse transformation" from one grid to the puzzles of the other. Then all puzzles will be in the same "coordinate system".
The task is complicated when one or both of the grids have automorphism level > 1.

Thread safety.
Since multi-core processors are popular, it is efficient to break long-running tasks into smaller chunks and distribute them to be executed in parallel on all available processors (when possible). If some procedure uses non-constant static data, then executing the same procedure concurrently on several processors (threads) will cause mess in this portion of the data. One simple solution is never to use static variables. Of course this has its own cost.
In order to avoid memory allocation/deallocation in the heap at each call to the minlex procedure, a static pointer is used, and the memory for the both transformation stacks is allocated only on the first call to the procedure. If, at the middle of the execution, a second processor (thread) started execution of the same piece of code, if will reinitialize the memory, currently used from the first processor (thread).
Code: Select all
   static Answer_t *Oldstk, *Newstk;

   if (!Oldstk)
   {
      if (!(Oldstk = (Answer_t*)malloc(2 * MAXANS * sizeof(Answer_t))))
         return;
      Newstk = Oldstk + MAXANS;
   }

In parallelizing my sudoku tools I am using OpenMP, which is easy to implement.

holdout wrote:*** A fast normalization algorithm could be useful for generation of all essentially different grids.

--- The algorithm I used to normalize full grids is certainly fast, but it may not be fast enough for your proposed applications.

This is a challenge. The art is a) to visit all 5472730538 grids in some optimal way, and b) to ensure you output the grid only once, not keeping huge history, where fast canonicalization could take place.

Another challenge is to find the most natural canonical form. Row-minlex is definitely the most human-friendly representation, but mathematically Anchor-5 form, with some still unknown additions, seems a better candidate.

I didn't understand the "dual key" concept. Hope it is some of the interesting details not described accurately in your article.

Congratulations for your innovative research. I am sure that during the coding you will find the best solutions of the remaining canonicalization problems (if such still exist :)).

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Postby Pat » Fri Aug 12, 2011 6:16 am

dobrichev wrote:
This is the distribution of grids by level of automorphism,
initially published by gsf
(sorry but I lost the link to the original post).

Code: Select all

1   5472170387
2   548449
3   7336
4   2826
6   1257
8   29
9   42
12   92
18   85
27   2
36   15
54   11
72   2
108   3
162   1
648   1


this was the old post --
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Two Row Minlex Rank

Postby dobrichev » Sat Aug 13, 2011 10:16 pm

Here are some statistics for the 2-row rank.

Bands.
The first column is zero based band number.
The rest 3 columns are zero based rank for the respective row pair.
Hidden Text: Show
Code: Select all
Band   r12   r13   r23
0   0   0   0
1   0   1   1
2   0   2   2
3   0   0   0
4   0   2   2
5   0   1   1
6   0   2   2
7   0   0   0
8   0   1   1
9   0   1   1
10   0   2   2
11   0   0   2
12   0   1   1
13   0   1   1
14   0   1   1
15   0   0   0
16   0   2   2
17   1   1   2
18   1   2   1
19   1   1   2
20   1   1   2
21   1   1   2
22   1   2   1
23   1   1   2
24   1   2   1
25   1   1   2
26   2   2   2
27   2   2   2
28   2   2   2
29   2   2   2
30   2   2   2
31   3   13   3
32   3   14   5
33   3   12   4
34   3   11   6
35   3   11   3
36   3   12   7
37   3   12   4
38   3   11   3
39   3   10   8
40   3   9   9
41   3   7   4
42   3   6   10
43   3   14   4
44   3   13   3
45   3   11   3
46   3   12   7
47   3   12   5
48   3   11   6
49   3   11   8
50   3   12   4
51   3   9   4
52   3   10   10
53   3   6   3
54   3   7   9
55   3   11   10
56   3   12   7
57   3   7   9
58   3   10   6
59   3   9   12
60   3   12   9
61   3   11   6
62   3   6   10
63   3   9   7
64   3   10   11
65   3   14   4
66   3   13   3
67   3   11   8
68   3   12   4
69   3   11   10
70   3   11   3
71   3   12   5
72   3   9   4
73   3   6   3
74   3   7   7
75   3   13   8
76   3   14   4
77   3   12   4
78   3   12   9
79   3   12   4
80   3   11   3
81   3   10   3
82   3   7   5
83   3   6   6
84   3   12   9
85   3   11   6
86   3   6   10
87   3   9   7
88   3   11   10
89   3   12   7
90   3   7   9
91   3   10   6
92   3   12   5
93   3   7   4
94   3   10   3
95   3   9   4
96   3   4   4
97   3   3   8
98   3   12   4
99   3   7   5
100   3   6   3
101   3   7   4
102   3   6   8
103   3   3   3
104   3   5   4
105   3   9   7
106   3   10   10
107   3   4   9
108   3   6   6
109   3   7   9
110   3   11   6
111   3   12   7
112   3   6   10
113   3   7   7
114   3   6   6
115   3   5   9
116   3   12   9
117   3   11   10
118   3   7   7
119   3   10   10
120   3   9   9
121   3   3   6
122   3   7   12
123   3   3   11
124   3   10   11
125   3   4   12
126   3   12   4
127   3   10   8
128   3   4   4
129   3   11   8
130   3   9   4
131   3   7   4
132   3   3   3
133   3   9   9
134   3   6   10
135   3   11   6
136   3   7   7
137   3   12   9
138   3   10   10
139   4   13   5
140   4   12   6
141   4   11   4
142   4   11   7
143   4   11   4
144   4   10   9
145   4   9   8
146   4   7   10
147   4   6   4
148   4   13   4
149   4   11   7
150   4   12   6
151   4   11   5
152   4   11   4
153   4   12   8
154   4   9   10
155   4   10   4
156   4   6   9
157   4   11   7
158   4   12   10
159   4   6   9
160   4   12   6
161   4   11   9
162   4   6   12
163   4   7   10
164   4   9   11
165   4   10   7
166   4   13   4
167   4   11   9
168   4   12   8
169   4   12   10
170   4   11   5
171   4   9   6
172   4   10   4
173   4   6   7
174   4   13   4
175   4   14   8
176   4   12   10
177   4   11   4
178   4   11   9
179   4   11   4
180   4   10   7
181   4   7   6
182   4   6   5
183   4   11   7
184   4   12   10
185   4   6   9
186   4   11   5
187   4   6   7
188   4   7   6
189   4   8   4
190   4   7   6
191   4   10   5
192   4   6   7
193   4   7   8
194   4   6   4
195   4   5   10
196   4   11   7
197   4   12   6
198   4   10   9
199   4   12   10
200   4   11   9
201   4   6   12
202   4   9   6
203   4   7   11
204   4   10   7
205   4   10   9
206   4   9   10
207   4   8   7
208   4   12   8
209   4   11   4
210   4   10   9
211   4   9   10
212   4   6   4
213   4   6   4
214   4   11   9
215   4   12   10
216   4   6   7
217   5   11   7
218   5   11   5
219   5   12   6
220   5   12   8
221   5   9   10
222   5   6   9
223   5   13   5
224   5   12   6
225   5   11   7
226   5   9   8
227   5   7   10
228   5   11   9
229   5   7   10
230   5   12   10
231   5   6   9
232   5   9   6
233   5   10   12
234   5   14   8
235   5   11   9
236   5   6   5
237   5   7   6
238   5   7   10
239   5   5   8
240   6   13   6
241   6   14   7
242   6   12   9
243   6   11   10
244   6   6   8
245   6   14   7
246   6   13   6
247   6   11   10
248   6   12   9
249   6   6   8
250   6   11   11
251   6   12   12
252   6   7   7
253   6   6   6
254   6   10   10
255   6   9   9
256   6   12   12
257   6   11   11
258   6   6   6
259   6   7   7
260   6   9   9
261   6   10   10
262   6   14   9
263   6   13   10
264   6   11   8
265   6   11   6
266   6   12   7
267   6   13   10
268   6   14   9
269   6   11   8
270   6   12   7
271   6   11   6
272   6   11   11
273   6   12   12
274   6   7   7
275   6   10   10
276   6   9   9
277   6   12   7
278   6   10   10
279   6   9   9
280   6   8   8
281   6   12   7
282   6   7   9
283   6   6   10
284   6   11   11
285   6   12   12
286   6   7   7
287   6   10   10
288   6   6   6
289   6   9   9
290   6   12   12
291   6   11   11
292   6   6   10
293   6   9   7
294   6   7   9
295   6   10   11
296   6   9   12
297   6   8   6
298   6   12   9
299   6   11   10
300   6   10   8
301   6   6   6
302   6   7   7
303   6   11   11
304   6   12   12
305   6   9   9
306   6   6   6
307   6   10   10
308   6   7   7
309   7   13   7
310   7   12   10
311   7   11   9
312   7   7   8
313   7   13   7
314   7   11   9
315   7   12   10
316   7   11   12
317   7   10   9
318   7   12   11
319   7   11   12
320   7   9   10
321   7   10   9
322   7   14   10
323   7   13   9
324   7   12   8
325   7   11   7
326   7   13   9
327   7   14   10
328   7   12   8
329   7   11   7
330   7   11   12
331   7   10   9
332   7   10   9
333   7   7   10
334   7   11   12
335   7   7   10
336   7   12   11
337   7   11   12
338   7   9   10
339   7   10   9
340   7   10   12
341   7   9   11
342   7   8   9
343   7   12   10
344   7   11   9
345   7   7   8
346   7   11   12
347   8   8   8
348   8   10   10
349   8   9   9
350   8   10   10
351   8   11   8
352   8   9   9
353   8   9   9
354   8   11   10
355   8   12   9
356   8   9   12
357   8   11   10
358   8   8   13
359   9   10   9
360   9   9   11
361   9   10   12
362   9   12   10
363   9   12   10
364   9   11   9
365   9   10   12
366   9   11   12
367   9   12   11
368   9   11   12
369   9   12   11
370   9   11   12
371   9   11   12
372   9   9   10
373   9   10   14
374   9   9   13
375   9   14   10
376   9   13   9
377   9   11   12
378   9   11   12
379   10   10   10
380   10   10   11
381   10   11   10
382   10   11   11
383   10   12   12
384   10   12   12
385   10   11   11
386   10   12   12
387   10   11   11
388   10   10   10
389   10   11   11
390   10   12   12
391   10   10   13
392   10   13   10
393   10   11   11
394   10   12   12
395   10   11   11
396   10   12   12
397   11   13   11
398   11   14   12
399   11   12   12
400   11   11   11
401   11   14   12
402   11   13   11
403   11   11   11
404   11   12   12
405   11   12   14
406   11   11   13
407   11   12   12
408   11   14   12
409   12   13   12
410   12   13   12
411   12   13   12
412   13   13   13
413   13   14   14
414   13   13   13
415   13   14   14


Grid distribution per minimal rank.
Code: Select all
Rank    Grids
0   488843212
1   519376601
2    68420279
3  3867134553
4   475255539
5    30137776
6    22132319
7     1376973
8       31987
9       20184
10       1077
11         34
12          3
13          1
14          0
=============
   5472730538

How to read the above table:
There are 488843212 essentially different grids having at least one row pair with rank 0.
There are 34 ED grids having no row pairs with rank 0..10 and having at least one row pair with rank 11.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: Two Row Minlex Rank

Postby holdout » Thu Aug 18, 2011 2:35 pm

dobrichev wrote:Here are some statistics for the 2-row rank.

Bands.
The first column is zero based band number.
The rest 3 columns are zero based rank for the respective row pair.
Code: Select all
Band   r12   r13   r23
0   0   0   0
1   0   1   1


Could you post an extra column to the 416-long hidden table?
The "gangster-44" number might be interesting.

holdout
holdout
 
Posts: 35
Joined: 30 August 2005
Location: Bowie, Maryland USA

Re: Two Row Minlex Rank

Postby dobrichev » Thu Aug 18, 2011 4:15 pm

holdout wrote:Could you post an extra column to the 416-long hidden table?
The "gangster-44" number might be interesting.

I never played directly with gangsters.

Maybe somebody can help, providing a (reference to) list with row-minlex band number and gangster number.
If there is some relationship with 2-row ranks I'll merge this column in the bands table.
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: Minlex Form: Min and Max Lists / Chaining

Postby coloin » Thu Aug 18, 2011 9:41 pm

coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Ranks for the 416 Bands and Gang-44

Postby dobrichev » Thu Aug 18, 2011 11:10 pm

zero based band number,
band in rowminlex canonical representation (from dukuso, not verified),
zero based two-row rank number for rows 12, 13, 23,
gang44 index (sorted)
Hidden Text: Show
Code: Select all
 band#                         digits r12 r13 r23  gang44
      0   123456789456789123789123456   0   0   0       1
    412   123456789457893612896127345  13  13  13       1
      1   123456789456789123789123465   0   1   1       2
    406   123456789457389621986721354  11  11  13       2
    413   123456789457893612896127354  13  14  14       2
     17   123456789456789132789123546   1   1   2       3
    390   123456789457389612896172345  10  12  12       3
    411   123456789457839612896271345  12  13  12       3
      2   123456789456789123789123645   0   2   2       4
    393   123456789457389612896712345  10  11  11       4
     26   123456789456789231789123645   2   2   2       5
    392   123456789457389612896271345  10  13  10       5
    165   123456789457189623689723154   4  10   7       6
    167   123456789457189623689723451   4  11   9       6
    201   123456789457189623986327451   4   6  12       6
    399   123456789457389621689721354  11  12  12       6
      3   123456789456789123789132465   0   0   0       7
     14   123456789456789123879213546   0   1   1       7
    131   123456789457189326689327154   3   7   4       7
    147   123456789457189326986327451   4   6   4       7
    163   123456789457189623689327154   4   7  10       7
    414   123456789457893612896217354  13  13  13       7
    415   123456789457893612986217354  13  14  14       7
      5   123456789456789123789213465   0   1   1       8
     18   123456789456789132789132654   1   2   1       8
    354   123456789457289631968137254   8  11  10       8
    387   123456789457389261986127534  10  11  11       8
    397   123456789457389612986127354  11  13  11       8
    408   123456789457398612896127354  11  14  12       8
    120   123456789457189263986327514   3   9   9       9
    177   123456789457189623698723154   4  11   4       9
    211   123456789457189632689723415   4   9  10       9
    223   123456789457189632896372415   5  13   5       9
    344   123456789457289631689731254   7  11   9       9
    365   123456789457298613689731245   9  10  12       9
    385   123456789457389216986127453  10  11  11       9
    398   123456789457389621689127345  11  14  12       9
    168   123456789457189623689723514   4  12   8      10
    199   123456789457189623986327145   4  12  10      10
    200   123456789457189623986327415   4  11   9      10
    334   123456789457289613896317245   7  11  12      10
    363   123456789457298613689137245   9  12  10      10
    377   123456789457298631968713425   9  11  12      10
      4   123456789456789123789132564   0   2   2      11
     23   123456789456789132798213456   1   1   2      11
     34   123456789457189236689327514   3  11   6      11
     35   123456789457189236689327541   3  11   3      11
     38   123456789457189236689723154   3  11   3      11
     40   123456789457189236689723451   3   9   9      11
     70   123456789457189236968732154   3  11   3      11
    126   123456789457189326689237154   3  12   4      11
    127   123456789457189326689237451   3  10   8      11
    128   123456789457189326689273154   3   4   4      11
    129   123456789457189326689273451   3  11   8      11
    133   123456789457189326689723145   3   9   9      11
    142   123456789457189326869327451   4  11   7      11
    150   123456789457189362689327415   4  12   6      11
    191   123456789457189623896723154   4  10   5      11
    204   123456789457189623986723145   4  10   7      11
    215   123456789457189632698372145   4  12  10      11
    258   123456789457198263896327514   6   6   6      11
    269   123456789457198362689723415   6  11   8      11
    282   123456789457198623896732145   6   7   9      11
    292   123456789457198632698327541   6   6  10      11
    376   123456789457298631896713245   9  13   9      11
    389   123456789457389612896127354  10  11  11      11
    410   123456789457398612896217354  12  13  12      11
    166   123456789457189623689723415   4  13   4      12
    202   123456789457189623986327514   4   9   6      12
    230   123456789457189632986237154   5  12  10      12
    231   123456789457189632986237451   5   6   9      12
    380   123456789457389126896127453  10  10  11      12
    401   123456789457389621869127354  11  14  12      12
     20   123456789456789132789231456   1   1   2      13
    388   123456789457389261986721354  10  10  10      13
    394   123456789457389612896712354  10  12  12      13
    189   123456789457189623896327451   4   8   4      14
    233   123456789457189632986327145   5  10  12      14
    239   123456789457198236698723415   5   5   8      14
    298   123456789457198632896237145   6  12   9      14
    307   123456789457289136968137452   6  10  10      14
    332   123456789457289613869713254   7  10   9      14
    341   123456789457289631689137254   7   9  11      14
    384   123456789457389162986721354  10  12  12      14
      8   123456789456789123798132546   0   1   1      15
      9   123456789456789123798132564   0   1   1      15
     33   123456789457189236689327154   3  12   4      15
     65   123456789457189236968237154   3  14   4      15
     74   123456789457189236986327154   3   7   7      15
     76   123456789457189236986327451   3  14   4      15
    123   123456789457189263986723514   3   3  11      15
    149   123456789457189362689327154   4  11   7      15
    151   123456789457189362689723154   4  11   5      15
    152   123456789457189362689723451   4  11   4      15
    198   123456789457189623968723154   4  10   9      15
    208   123456789457189632689327154   4  12   8      15
    254   123456789457198263698327415   6  10  10      15
    381   123456789457389126986721543  10  11  10      15
    395   123456789457389612896721354  10  11  11      15
    404   123456789457389621896217354  11  12  12      15
    370   123456789457298613896317245   9  11  12      16
     19   123456789456789132789213654   1   1   2      17
     27   123456789456789231789132546   2   2   2      17
     86   123456789457189263689723415   3   6  10      17
    219   123456789457189632896237145   5  12   6      17
    220   123456789457189632896237415   5  12   8      17
    272   123456789457198623689237154   6  11  11      17
    391   123456789457389612896172354  10  10  13      17
    405   123456789457389621986271345  11  12  14      17
     22   123456789456789132789321564   1   2   1      18
     39   123456789457189236689723415   3  10   8      18
     55   123456789457189236869732451   3  11  10      18
     75   123456789457189236986327415   3  13   8      18
    153   123456789457189362689723514   4  12   8      18
    154   123456789457189362698237415   4   9  10      18
    209   123456789457189632689327514   4  11   4      18
    281   123456789457198623896723541   6  12   7      18
    284   123456789457198623968237145   6  11  11      18
    349   123456789457289631869731254   8   9   9      18
    362   123456789457298361986731524   9  12  10      18
    368   123456789457298613869317245   9  11  12      18
    382   123456789457389162896217435  10  11  11      18
    409   123456789457398612896172354  12  13  12      18
    212   123456789457189632689723514   4   6   4      19
    305   123456789457289136869731254   6   9   9      19
    329   123456789457289613698317254   7  11   7      19
    113   123456789457189263968327514   3   7   7      20
    121   123456789457189263986372451   3   3   6      20
    181   123456789457189623869273145   4   7   6      20
    187   123456789457189623896237514   4   6   7      20
    378   123456789457298631986137542   9  11  12      20
    216   123456789457189632698732541   4   6   7      21
    310   123456789457289163689713254   7  12  10      21
    325   123456789457289613689173254   7  11   7      21
    375   123456789457298631896137524   9  14  10      21
     36   123456789457189236689372451   3  12   7      22
     77   123456789457189236986372154   3  12   4      22
     78   123456789457189236986372451   3  12   9      22
     94   123456789457189263869273145   3  10   3      22
    117   123456789457189263968723514   3  11  10      22
    124   123456789457189263986732154   3  10  11      22
    331   123456789457289613869173452   7  10   9      22
    352   123456789457289631896317254   8   9   9      22
    383   123456789457389162986712345  10  12  12      22
     68   123456789457189236968327514   3  12   4      23
     71   123456789457189236968732541   3  12   5      23
     97   123456789457189263869327514   3   3   8      23
    157   123456789457189362869327415   4  11   7      23
    162   123456789457189623689273541   4   6  12      23
    188   123456789457189623896327145   4   7   6      23
    190   123456789457189623896327514   4   7   6      23
    253   123456789457198263689732541   6   6   6      23
    299   123456789457198632896237514   6  11  10      23
    322   123456789457289316986137542   7  14  10      23
    338   123456789457289613986173254   7   9  10      23
    339   123456789457289613986173542   7  10   9      23
    351   123456789457289631896317245   8  11   8      23
    182   123456789457189623869273451   4   6   5      24
    186   123456789457189623896237451   4  11   5      24
    240   123456789457198236698732415   6  13   6      24
    274   123456789457198623698372145   6   7   7      24
    300   123456789457198632986237145   6  10   8      24
    308   123456789457289136968137542   6   7   7      24
    316   123456789457289163896137425   7  11  12      24
    328   123456789457289613689371254   7  12   8      24
     83   123456789457189263689273415   3   6   6      25
    100   123456789457189263869723415   3   6   3      25
    158   123456789457189362896372451   4  12  10      25
    207   123456789457189632689273154   4   8   7      25
    222   123456789457189632896327451   5   6   9      25
    224   123456789457189632896732541   5  12   6      25
    228   123456789457189632968327415   5  11   9      25
    234   123456789457189632986372154   5  14   8      25
    266   123456789457198326986372145   6  12   7      25
    278   123456789457198623896237154   6  10  10      25
    288   123456789457198623986732541   6   6   6      25
    321   123456789457289316986137452   7  10   9      25
    330   123456789457289613869173254   7  11  12      25
    402   123456789457389621869721345  11  13  11      25
     82   123456789457189263689273154   3   7   5      26
     84   123456789457189263689273451   3  12   9      26
    337   123456789457289613986137245   7  11  12      26
    356   123456789457289631968731245   8   9  12      26
     52   123456789457189236869327514   3  10  10      27
     85   123456789457189263689273514   3  11   6      27
    161   123456789457189362986273154   4  11   9      27
    217   123456789457189632869327145   5  11   7      27
    252   123456789457198263689732154   6   7   7      27
    279   123456789457198623896237514   6   9   9      27
    280   123456789457198623896273415   6   8   8      27
    301   123456789457198632986237154   6   6   6      27
    324   123456789457289361986173452   7  12   8      27
    369   123456789457298613896137524   9  12  11      27
     24   123456789456789132798231546   1   2   1      28
     43   123456789457189236698237145   3  14   4      28
     44   123456789457189236698237415   3  13   3      28
     63   123456789457189236896723514   3   9   7      28
     95   123456789457189263869273451   3   9   4      28
     96   123456789457189263869273514   3   4   4      28
    104   123456789457189263896723541   3   5   4      28
    357   123456789457289631986137245   8  11  10      28
    358   123456789457289631986731245   8   8  13      28
    225   123456789457189632968237415   5  11   7      29
    350   123456789457289631896137425   8  10  10      29
    366   123456789457298613698713245   9  11  12      29
    373   123456789457298631698731245   9  10  14      29
     53   123456789457189236869372415   3   6   3      30
     60   123456789457189236896372145   3  12   9      30
    122   123456789457189263986372541   3   7  12      30
    226   123456789457189632968273154   5   9   8      30
    245   123456789457198236896372541   6  14   7      30
     32   123456789457189236689273541   3  14   5      31
     37   123456789457189236689372514   3  12   4      31
     49   123456789457189236698372145   3  11   8      31
     54   123456789457189236869732145   3   7   9      31
     64   123456789457189236896732415   3  10  11      31
     73   123456789457189236986273541   3   6   3      31
     79   123456789457189236986372514   3  12   4      31
    115   123456789457189263968372451   3   5   9      31
    116   123456789457189263968723451   3  12   9      31
    136   123456789457189326698237541   3   7   7      31
    138   123456789457189326869237514   3  10  10      31
    139   123456789457189326869237541   4  13   5      31
    141   123456789457189326869273541   4  11   4      31
    144   123456789457189326869732415   4  10   9      31
    145   123456789457189326896237415   4   9   8      31
    159   123456789457189362968372514   4   6   9      31
    160   123456789457189362986237514   4  12   6      31
    169   123456789457189623689732415   4  12  10      31
    176   123456789457189623698723145   4  12  10      31
    179   123456789457189623698732154   4  11   4      31
    213   123456789457189632689732415   4   6   4      31
    229   123456789457189632968372145   5   7  10      31
    276   123456789457198623698732154   6   9   9      31
    287   123456789457198623968732154   6  10  10      31
    290   123456789457198632689732154   6  12  12      31
    295   123456789457198632869327541   6  10  11      31
    326   123456789457289613689317425   7  13   9      31
    346   123456789457289631698371452   7  11  12      31
     10   123456789456789123798213564   0   2   2      32
     25   123456789456789132879231564   1   1   2      32
     41   123456789457189236689732514   3   7   4      32
     42   123456789457189236689732541   3   6  10      32
     48   123456789457189236698327145   3  11   6      32
     56   123456789457189236869732541   3  12   7      32
     67   123456789457189236968327154   3  11   8      32
     99   123456789457189263869372451   3   7   5      32
    156   123456789457189362869237514   4   6   9      32
    164   123456789457189623689372514   4   9  11      32
    170   123456789457189623698237154   4  11   5      32
    195   123456789457189623896732451   4   5  10      32
    205   123456789457189623986732415   4  10   9      32
    210   123456789457189632689372145   4  10   9      32
    235   123456789457198236689237451   5  11   9      32
    241   123456789457198236869273541   6  14   7      32
    246   123456789457198236968237451   6  13   6      32
    255   123456789457198263869327451   6   9   9      32
    259   123456789457198263896732514   6   7   7      32
    263   123456789457198263986732541   6  13  10      32
    289   123456789457198632689327154   6   9   9      32
    345   123456789457289631698371245   7   7   8      32
     13   123456789456789123798312564   0   1   1      33
     21   123456789456789132789231564   1   1   2      33
     31   123456789457189236689237514   3  13   3      33
     47   123456789457189236698273541   3  12   5      33
     51   123456789457189236869237415   3   9   4      33
     57   123456789457189236896237145   3   7   9      33
     58   123456789457189236896237415   3  10   6      33
     72   123456789457189236986237514   3   9   4      33
     80   123456789457189263689237145   3  11   3      33
     92   123456789457189263698732415   3  12   5      33
    109   123456789457189263968273154   3   7   9      33
    111   123456789457189263968273451   3  12   7      33
    118   123456789457189263968732451   3   7   7      33
    132   123456789457189326689372541   3   3   3      33
    135   123456789457189326689732541   3  11   6      33
    143   123456789457189326869723541   4  11   4      33
    146   123456789457189326986273145   4   7  10      33
    148   123456789457189362689237541   4  13   4      33
    175   123456789457189623698372154   4  14   8      33
    193   123456789457189623896723541   4   7   8      33
    194   123456789457189623896732145   4   6   4      33
    206   123456789457189632689237145   4   9  10      33
    243   123456789457198236869732145   6  11  10      33
    264   123456789457198326698732451   6  11   8      33
    273   123456789457198623698237451   6  12  12      33
    407   123456789457398216986217354  11  12  12      33
     12   123456789456789123798231564   0   1   1      34
     88   123456789457189263698327415   3  11  10      34
    103   123456789457189263896372145   3   3   3      34
    125   123456789457189263986732541   3   4  12      34
    237   123456789457198236689327154   5   7   6      34
    251   123456789457198236986732541   6  12  12      34
    304   123456789457289136689713542   6  12  12      34
    315   123456789457289163869317245   7  12  10      34
    335   123456789457289613896731254   7   7  10      34
     87   123456789457189263689732514   3   9   7      35
     89   123456789457189263698372154   3  12   7      35
     90   123456789457189263698723451   3   7   9      35
     91   123456789457189263698732154   3  10   6      35
     93   123456789457189263698732541   3   7   4      35
    119   123456789457189263986237514   3  10  10      35
    155   123456789457189362698327514   4  10   4      35
    172   123456789457189623698273514   4  10   4      35
    173   123456789457189623698327514   4   6   7      35
    174   123456789457189623698327541   4  13   4      35
    185   123456789457189623869732541   4   6   9      35
    218   123456789457189632869327154   5  11   5      35
    232   123456789457189632986273415   5   9   6      35
    238   123456789457198236689372154   5   7  10      35
    244   123456789457198236896273154   6   6   8      35
    249   123456789457198236986273415   6   6   8      35
    260   123456789457198263968273145   6   9   9      35
    262   123456789457198263986327415   6  14   9      35
    265   123456789457198326968723514   6  11   6      35
    275   123456789457198623698372514   6  10  10      35
    286   123456789457198623968723145   6   7   7      35
    294   123456789457198632869237451   6   7   9      35
    297   123456789457198632869723154   6   8   6      35
    323   123456789457289361869713524   7  13   9      35
    347   123456789457289631698713452   8   8   8      35
    361   123456789457298316698137254   9  10  12      35
    367   123456789457298613698731254   9  12  11      35
    372   123456789457298613986371254   9   9  10      35
    374   123456789457298631869713254   9   9  13      35
    386   123456789457389261896217534  10  12  12      35
     59   123456789457189236896237514   3   9  12      36
    101   123456789457189263869732145   3   7   4      36
    102   123456789457189263869732451   3   6   8      36
    134   123456789457189326689732415   3   6  10      36
    140   123456789457189326869273451   4  12   6      36
    171   123456789457189623698273145   4   9   6      36
    184   123456789457189623869732451   4  12  10      36
    221   123456789457189632896273451   5   9  10      36
    227   123456789457189632968327154   5   7  10      36
    236   123456789457198236689273154   5   6   5      36
    247   123456789457198236986237154   6  11  10      36
    261   123456789457198263986237514   6  10  10      36
    271   123456789457198362896732154   6  11   6      36
    277   123456789457198623869327415   6  12   7      36
    283   123456789457198623896732541   6   6  10      36
    293   123456789457198632869237415   6   9   7      36
    302   123456789457198632986372145   6   7   7      36
    371   123456789457298613968713254   9  11  12      36
    400   123456789457389621698127345  11  11  11      36
    403   123456789457389621896172543  11  11  11      36
     61   123456789457189236896372154   3  11   6      37
     98   123456789457189263869372415   3  12   4      37
    105   123456789457189263896732154   3   9   7      37
    106   123456789457189263896732451   3  10  10      37
    107   123456789457189263968237514   3   4   9      37
    108   123456789457189263968237541   3   6   6      37
    110   123456789457189263968273415   3  11   6      37
    178   123456789457189623698723514   4  11   9      37
    183   123456789457189623869372415   4  11   7      37
    196   123456789457189623896732514   4  11   7      37
    197   123456789457189623968327415   4  12   6      37
    203   123456789457189623986372145   4   7  11      37
    214   123456789457189632689732541   4  11   9      37
    242   123456789457198236869723154   6  12   9      37
    248   123456789457198236986237415   6  12   9      37
    285   123456789457198623968372145   6  12  12      37
    303   123456789457198632986732514   6  11  11      37
    317   123456789457289163896317524   7  10   9      37
    327   123456789457289613689371245   7  14  10      37
    336   123456789457289613968731425   7  12  11      37
    343   123456789457289631689713245   7  12  10      37
    348   123456789457289631869713524   8  10  10      37
    353   123456789457289631896371254   8   9   9      37
    359   123456789457298136869173254   9  10   9      37
    360   123456789457298136986317245   9   9  11      37
    364   123456789457298613689713245   9  11   9      37
     11   123456789456789123798213654   0   0   2      38
     30   123456789456789231798312654   2   2   2      38
     45   123456789457189236698273145   3  11   3      38
     46   123456789457189236698273415   3  12   7      38
     66   123456789457189236968273145   3  13   3      38
    267   123456789457198362689237154   6  13  10      38
    268   123456789457198362689237451   6  14   9      38
    270   123456789457198362869273451   6  12   7      38
    312   123456789457289163698173542   7   7   8      38
    340   123456789457289613986731245   7  10  12      38
    396   123456789457389612968127354  10  12  12      38
    112   123456789457189263968327145   3   6  10      39
    306   123456789457289136896371254   6   6   6      39
    311   123456789457289163698137524   7  11   9      39
    313   123456789457289163698317254   7  13   7      39
    318   123456789457289163896731254   7  12  11      39
    320   123456789457289163968731542   7   9  10      39
     29   123456789456789231789312456   2   2   2      40
    309   123456789457289163689173452   7  13   7      40
      6   123456789456789123789231564   0   2   2      41
     16   123456789456789123897231645   0   2   2      41
     62   123456789457189236896723451   3   6  10      41
     81   123456789457189263689237514   3  10   3      41
    250   123456789457198236986723415   6  11  11      41
    256   123456789457198263896237154   6  12  12      41
    257   123456789457198263896237451   6  11  11      41
    355   123456789457289631968317245   8  12   9      41
      7   123456789456789123789231645   0   0   0      42
     28   123456789456789231789231564   2   2   2      42
     50   123456789457189236698372541   3  12   4      42
     69   123456789457189236968372514   3  11  10      42
    130   123456789457189326689273514   3   9   4      42
    137   123456789457189326698372154   3  12   9      42
    192   123456789457189623896723415   4   6   7      42
    291   123456789457198632698237154   6  11  11      42
    379   123456789457389126698172354  10  10  10      42
    114   123456789457189263968372145   3   6   6      43
    180   123456789457189623698732514   4  10   7      43
    296   123456789457198632869372154   6   9  12      43
    314   123456789457289163698713254   7  11   9      43
    333   123456789457289613869731524   7   7  10      43
    342   123456789457289631689173245   7   8   9      43
     15   123456789456789123897231564   0   0   0      44
    319   123456789457289163968317245   7  11  12      44
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Next

Return to Software