Serg wrote:I am still thinking about efficient LS canonicalization algorithm.
It's not important - has a LS grid UA4/UA6 or no. But we should know smallest size of its two-row UA set.
Let, for example, the smallest size of LS grid's two-row UA set is 8 (UA8). In this case we can be sure that r1 and r2 LS rows will have such view:
- Code: Select all
123456789
234167895
I have no proof of this statement right now though. But it's very likely.
If it's true, the columns order is fixed, and we get rid of 9! column permutations.
In this case, you can cycle the columns in the UA8 and (independently) in the UA10 (and relabel).
That gives 4*5 = 20 column permutations, to check.
The worst case is 2 rows with 3 UA6's -- 6*3*3*3 = 162 column permutations, to check.
The factor of 6, comes from 6 ways to order the UA6's.
The 2nd worst case is two rows with 3 UA4's and a UA6 -- 6*2*2*2*3 = 144 column permutations, to check.
The worst case happens (many times) in the MC grid.
Each pair of rows has 3 UA6's, and as you say, the rows can be taken in either order.
The total number of checks is 6*72*162 = 69984, where the factor of 6 comes from "6 conjugates".
[ It turns out that the MC grid has 69984/3 = 23328 automorphisms. ]
Cheers,
Blue.
)
