I would like to efficiently generate all words length N (N is prime) excluding isomorphic one.
Word A isomorphic to word B if there is an Automorphism for Finite Cyclic group with N elements that convert word A to the word B.
Let V - is an alphabet of K elements.
For example V = {a,b}
Let N is 7
Then, for example the word A = {a,a,a,b,b,a,a} is isomorphic to the word B = {a,b,a,a,a,a,b} and word C= {a,a,b,a,a,b,a} because Finite Cycle group S= {0, 1, 2, 3, 4, 5, 6} has automorphisms {0, 4, 1, 5, 2, 6, 3} and {0, 5, 3, 1, 6, 4, 2}
The simplest algorithm is
- to find all possible words
- find all automorphism for Finite Cycle group with N elements (N prime)
- exclude isomorphic words
Unfortunately this way is not algorithmically efficient.
If your objection to the simple algorithm is needing to store all of the unique words, that's not necessary. For each of the K^N words, test whether it's lexicographically less than or equal to all of its isomorphs (canonical), and if so, return it.
We can do better by
Generating all canonical (N−1)-letter suffixes and appending each all possible first letters.
Generating (N−1)-letter suffixes by iterating the second position through the possible letters and generating suffixes where the other letters are not less than the second position before testing for canonicity as above.
We could go further but I'm suspicious about whether the added complexity would pay for itself.