Message Boards Message Boards

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

generating distincts permutations under a symmetry group

Luc Barthelet, Makena
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?

Luc
POSTED BY: Luc Barthelet
3 Replies
Sort By:
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}
Danny
POSTED BY: Daniel Lichtblau
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,
Luc
POSTED BY: Luc Barthelet
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.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract