Message Boards Message Boards

3 Replies
6 Total Likes
View groups...
Share this post:

generating distincts permutations under a symmetry group

Posted 12 years ago
I am interested in generating all the ordered ways to fill a 3x3 matrix.

 1  2  3
 4  5  6
 7  8  9

and Permutations[ Range[9]] does a fine job generating the 362880 permutations

I now would like to do this, but to take into account the all the symmetries, which should limit me to 45360 since GroupOrder[DihedralGroup[4]] =8

But how do I generate a distinct set of those permutations under the dihedralGroup[4] symmetry?

POSTED BY: Luc Barthelet
3 Replies
Danny, thank you for the quick and very effective response.

This got me thinking about the generic way.

Clearly, we need some definition of the group, as applied to the representation, in my case:
d4Group = PermutationGroup[{Cycles[{{1, 3, 9, 7}, {2, 6, 8, 4}}], Cycles[{{2, 6}, {4, 8}, {1, 9}}] }]

Then we can generate the orbits for each permutation and just keep the distinct ones:
 allDistinctPermutations = First /@ Union[ GroupOrbits[ d4Group, Permutations[Range[9]]]] 

the whole thing only takes 40% longer than the specific Select

thank you Danny,
POSTED BY: Luc Barthelet
Easiest just to generate all of them and then cull out a "canonical" set of coset representatives. One way is to enforce that the top left corner be less than the other three corners (a rotation would give one such representative) and that the top right be less than the bottom left (a reflection would give that).
In[165]:= Timing[pm = Permutations[Range[9]];]
Out[165]= {0.010000, Null}

In[166]:= Length[pm]
Out[166]= 362880

In[174]:= Timing[Length[symm = Select[pm, (#[[1]] < #[[3]] < #[[7]] && #[[1]] < #[[9]]) &]]]
Out[174]= {1.140000, 45360}
POSTED BY: Daniel Lichtblau
This is rather neat - the question and the answer. The only thing I could come up with was explicitly defining symmetry operators, explicitly generating symmetries subset and then excluding that from the original permutation set. That would be terribly cumbersome - Danny's answer is so simple.
POSTED BY: Vitaliy Kaurov
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract