Background

I want to get a permutation list, so I use the SymmetricGroup(or use Permutations) to produce it when the GroupOrder is 4.

Permute[Range@4, SymmetricGroup[4]]


{{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,3,4,2},{1,4,2,3},{1,4,3,2},{2,1,3,4},{2,1,4,3},{2,3,1,4},{2,3,4,1},{2,4,1,3},{2,4,3,1},{3,1,2,4},{3,1,4,2},{3,2,1,4},{3,2,4,1},{3,4,1,2},{3,4,2,1},{4,1,2,3},{4,1,3,2},{4,2,1,3},{4,2,3,1},{4,3,1,2},{4,3,2,1}}

You can use Permutations[Range@4] to get the same list. But when the GroupOrder surpass 11, my PC cannot generate such permutation list because of the insufficient RAM. So I want to split it into more part then process it respectively and combine those parts in the last work.

Question

How to split a SymmetricGroup into some PermutationGroup with smaller GroupOrder. These new PermutationGroup had better have no overlapping GroupElements and all of the PermutationGroup's GroupElements is equal to that of SymmetricGroup's.

• What do you mean by "process it?" – Jens Jun 16 '16 at 15:56

A permutation group cannot be partitioned into a list of disjoint permutation groups. Note for example that every permutation group must necessarily contain the identity permutation.

But we can partition a group G into a subgroup S and cosets of S in G. For symmetric groups this is easy, because we know that if m < n the SymmetricGroup[m] is a subgroup of SymmetricGroup[n]. This allows breaking the list of n! permutations of SymmetricGroup[n] into n disjoint lists of (n-1)! permutations each.

To do this, we need to construct the list of "coset representatives":

representatives[n_Integer] := Table[Cycles[{Range[i, n]}], {i, n, 1, -1}]


and the following function to construct cosets by permutation product:

rightcoset[groupelems_List, perm_Cycles] := Thread[PermutationProduct[groupelems, perm]]


Now imagine that you already have the list of group elements of SymmetricGroup[6]:

S6 = GroupElements[SymmetricGroup[6]]


Create the seven cosets of S6 in S7 (in your application you would construct and work with one coset at a time):

S7cosets = rightcoset[S6, #] & /@ representatives[7]


The full list of elements of the group is just the joining of those lists:

S7 = Join@@ S7cosets


Check that we indeed have them all:

In[]:= Sort[S7] === Sort[GroupElements[SymmetricGroup[7]]]
Out[]= True

• This answer help me a lot.I cost plenty of time to digest your answer,and I have consulted some books for understanding it.Thanks very very much. – yode Jun 18 '16 at 20:19
• Would you mind to update an universal method to partition any group G into a subgroup S and cosets of S in G?such as this group,SeedRandom[1]; group=PermutationGroup[{RandomPermutation[4],RandomPermutation[5],RandomPermutation[7]}].Of course,maybe I should be post a new question for this. – yode Jun 19 '16 at 6:32