How to generate all $ 3 \times 3 $ matrices with $ a,a,a,a,b,b,b,c,c $?
A brute force approach:
For a permutation p
, protations[p]
constructs the union of permutations obtained by all possible two-step rotations of its 8 elements after dropping its middle element. We use MemberQ[protations[#], #2]&
as the test function in DeleteDuplicates
. Then using Partition[#, 3]&
for all permutations in the resulting list gives the desired list of 3X3 matrices.
lst = {a, a, a, a, b, b, b, c, c};
perms = Permutations[{a, a, a, a, b, b, b, c, c}];
Length @ perms
1260
Borrowing the idea that we can consider the last element of permutation as the center of the matrix from @jose's answer:
ClearAll[protations]
protations[x_] := Module[{l = Length[x]},
Union @ (RotateRight[Most @ x, #] & /@ Range[0, l - 2, 2])]
dupetest = MemberQ[protations[#], Most @ #2] &;
out = DeleteDuplicates[perms, dupetest];
Length @ out
318
10 examples:
Row[MatrixForm[Partition[Insert[Most@#, Last@#, 5], 3]] & /@ RandomSample[out, 10]]
An alternative test function using GroupOrbits
(again from jose's answer) of the PermutationGroup
of a subset of the group elements of CyclicGroup
:
pg = PermutationGroup[GroupElements[CyclicGroup[8]][[;; ;; 2]]]
dupetest2 = MemberQ[First@GroupOrbits[pg, {Most@#}, Permute], Most@#2] &;
out2 = DeleteDuplicates[perms, dupetest2];
out2 == out
True
A much faster approach is to generate GroupOrbits
of pg
for perms
at once (again from jose's answer) and take the first element of each orbit.
out3 = GroupOrbits[pg, perms, Permute][[All, 1]];
out3 == out
True
Let me give a GroupOrbits approach, imitating many aspects of the accepted solution. Start again with all permutations of the elements:
list = {a, a, a, a, b, b, b, c, c};
perms = Permutations[list];
Again, assume each permutation defines a matrix whose central element is placed last:
makeMatrix[{e1_, e2_, e3_, e4_, e5_, e6_, e7_, e8_, e9_}] := {{e1, e2, e3}, {e8, e9, e4}, {e7, e6, e5}}
Then we can partition the lists into orbits of equivalent cases under cyclic permutation of the first eight elements:
In[]:= Length[orbits = GroupOrbits[CyclicGroup[8], perms, Permute]]
Out[]= 159
Select some examples of orbit representatives with
MatrixForm /@ makeMatrix /@ First /@ RandomSample[orbits, 10]