How to generate all $ 3 \times 3 $ matrices with $ a,a,a,a,b,b,b,c,c $, which can not be obtained from each other by rotation transformation?
$\begingroup$
$\endgroup$
6
2 Answers
$\begingroup$
$\endgroup$
6
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
-
$\begingroup$ Thank you! What does “@Range[-7,7]” mean in the code? $\endgroup$– King.MaxSep 3, 2019 at 12:04
-
$\begingroup$ @King.Max,` RotateRight[list, -k]` is the same as
RotateLeft[list, k](rotate to the left k positions).RotateRight[{a, b, c, d}, #] & /@ Range[-3, 3]gives list of all possible rotations of the 4 element list{a, b, c, d}. $\endgroup$– kglrSep 3, 2019 at 13:02 -
$\begingroup$ Same as the question I asked below: if one of the matrices is like this：$\left(\begin{array}{lll}{1} & {2} & {3} \\ {8} & {9} & {4} \\ {7} & {6} & {5}\end{array}\right)$ . I know that such a matrix $\left(\begin{array}{lll}{3} & {4} & {5} \\ {2} & {9} & {6} \\ {1} & {8} & {7}\end{array}\right)$ will be treated the same. But such a matrix $\left(\begin{array}{lll}{2} & {3} & {4} \\ {1} & {9} & {5} \\ {8} & {7} & {6}\end{array}\right)$ ,I don't want it to be considered the same. Will it be considered as the same matrix in your code and deleted? $\endgroup$– King.MaxSep 4, 2019 at 2:42
-
$\begingroup$ I mean, when a matrix is rotated 90,180，270 or 360degrees, we think it is equivalent, and the other we think they are not equivalent. $\endgroup$– King.MaxSep 4, 2019 at 2:52
-
$\begingroup$ @King.Max, this is important piece of information; you should add this to your question. As is, both answers consider the third matrix sames as the first two. You can change
Range[0, l - 2]inprotationstoRange[0, l - 2, 2]to handle equivalence by "90,180，270 or 360 Degree" rotations. $\endgroup$– kglrSep 4, 2019 at 3:13
$\begingroup$
$\endgroup$
3
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]
-
$\begingroup$ But I have a problem: if one of the matrices is like this：$\left(\begin{array}{lll}{1} & {2} & {3} \\ {8} & {9} & {4} \\ {7} & {6} & {5}\end{array}\right)$ . I know that such a matrix $\left(\begin{array}{lll}{3} & {4} & {5} \\ {2} & {9} & {6} \\ {1} & {8} & {7}\end{array}\right)$ will be treated the same. But such a matrix $\left(\begin{array}{lll}{2} & {3} & {4} \\ {1} & {9} & {5} \\ {8} & {7} & {6}\end{array}\right)$ ,I don't want it to be considered the same. Will it be considered as the same matrix in your code and deleted? $\endgroup$– King.MaxSep 4, 2019 at 2:40
-
2$\begingroup$ To consider that situation you need a different permutation group: instead of using CyclicGroup[8], use PermutationGroup[{Cycles[{{1,3,5,7}, {2,4,6,8}}]}]. There are then 318 different orbits, because each of the previous 159 orbits breaks in two. $\endgroup$– joseSep 4, 2019 at 6:51
-
res = Permutations[{a, a, a, a, b, b, b, c, c}]; res = ArrayReshape[#, {3, 3}] & /@ res; MatrixForm[#] & /@ res? To check for the last partwhich can not be obtained each other by rotation transformationis something not included in the above code. How would you check for this part? $\endgroup$