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]]

enter image description here

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]

Tags:

Matrix