Usage of permutation groups conjugacy classes is rather common practice when people solve any kinds of sudoku enumeration problems. See, for example, famous article There are 5472730538 essentially different Sudoku grids ... and the Sudoku symmetry group by Ed Russell and Frazer Jarvis, or JPF's investigations of essentially different sudoku patterns' numbers (see his posts in the threads One-band patterns and Number of non equivalent patterns having N clues). When people use Burnside's Lemma to calculate (enumerate) essentially different entities, such as sudoku grids, sudoku patterns, etc., knowing conjugacy classes can dramatically shorten time necessary for calculation of those entities, because one sample permutation only from every conjugacy class should be analyzed during such calculation.
It turns out, that conjugacy classes is not the only division of permutation group that can be useful during sudoku enumeration problems solving. I propose to consider another equivalence classes system which can be called as "cycle factorization classes". This equivalence classes system is not so universal as conjugacy classes system, and cannot be used, for example, for essentially different sudoku grids enumeration. But it is quite useful during essentially different sudoku patterns enumeration.
I mean well-known complete factorization into disjoint cycles for permutations (see, for example, book "An Introduction to the Theory of Groups" by Joseph J. Rotman). Two permutations are treated equivalent when they have equal numbers of cycles for each length of cycles present in complete factorization into disjoint cycles for these permutations. Let's consider, for example, 2 sample permutations from 275 conjugacy classes, published by Ed Russell and Frazer Jarvis (see the link above).
- Code: Select all
(1 10 19)(2 12 20 3 11 21)(4 13 22)(5 15 23 6 14 24)(7 18 26)(8 16 27)(9 17 25)(28 37 46)(29 39 47 30 38 48)(31 40 49)(32 42 50 33 41 51)(34 45 53)(35 43 54)(36 44 52)(55 64 73)(56 66 74 57 65 75)(58 67 76)(59 69 77 60 68 78)(61 72 80)(62 70 81)(63 71 79) - sample permutation of conjugacy class 20
(1 10 19)(2 12 20 3 11 21)(4 13 22)(5 15 23 6 14 24)(7 16 25)(8 17 26)(9 18 27)(28 37 46)(29 39 47 30 38 48)(31 40 49)(32 42 50 33 41 51)(34 43 52)(35 44 53)(36 45 54)(55 73 64)(56 75 65 57 74 66)(58 76 67)(59 78 68 60 77 69)(61 79 70)(62 80 71)(63 81 72) - sample permutation of conjugacy class 21
Each of these permutations has 15 cycles of length 3 and 6 cycles of length 6. So, both permutations should be treated as equivalent and should belong to the same equivalence class when we use "cycle factorization classes" system. Each cycle factorization class contains one or more conjugacy classes as whole. When we consider symmetric group of permutations (for example, S81 - group of all possible permutations of sudoku grid digits), conjugacy classes system and cycle factorization classes system coincide exactly, but if we consider subgroup of symmetric group (for example, group of VPT, which is subgroup of symmetric group S81), both systems differ substaintially. For VPT group conjugacy classes system gives 275 equivalence classes, but cycle factorization classes system gives 163 classes only (some conjugacy classes must be united to form one cycle factorization class).
So, that 163 cycle factorization classes can be used during calculation number of e-d patterns instead of 275 conjugacy classes. It is more convenient to use less equivalence classes. But cycle factorization classes system has much more valuable advantage - to compute cycle factorization classes we need only |G| operations (|G| - order of the considered group). But we must use |G|^2 operations when we compute conjugacy classes (each set's element must be multiplied by each set's element to check conjugacy; but maybe there exist much more efficient algorithms of conjugacy classes division?)
In any way I calculated those 163 cycle factorization classes for VPT group (see attachment) and test them during calculation of essentially different patterns. I got the same number (746186061249180790 e-d patterns) as Red Ed and JPF (see thread One-band patterns).
Classification VPT group into cycle factorization classes took me 28 seconds of CPU time.
Serg
