6
$\begingroup$

Here is my permutation group that acts on lists of length 4, defined in terms of four generators:

permGroup = PermutationGroup[{Cycles[{{1, 3}, {2, 4}}], 
                Cycles[{{1, 2}}], Cycles[{{3, 4}}], Cycles[{{2, 4}}]}]

Given a list of four entires out of order, I can get the permutation required using FindPermutation or the position of the element in the group using GroupElementPosition:

outOfOrderExample = {3,1,2,4};

GroupElementPosition[permGroup, FindPermutation[outOfOrderExample,{1,2,3,4}]]
(*13*)

But, how do I get the precise sequence of group generators that when multiplied together puts the list outOfOrderExample back in order? Obviously, the answer is not unique. I just need any of the shortest answer.

An acceptable answer would be a list of numbers identifying the generators in permGroup, such as {2, 3, 4, 3} for this example. You can check the answer is correct by doing something like

Permute[outOfOrderExample,
   PermutationProduct@@First[permGroup][[{2, 3, 4, 3}]]]
$\endgroup$
6
$\begingroup$

Use GroupElementToWord. There are some examples in the documentation, especially in the Neat Examples section which mentions Rubik's cube.

Below I express the permutation that takes {3,1,2,4} to {1,2,3,4} in terms of a 'word' or sequence of the group generators (and their inverses).

perms = {
  Cycles[{{1, 3}, {2, 4}}],
  Cycles[{{1, 2}}],
  Cycles[{{3, 4}}],
  Cycles[{{2, 4}}]
};

permGroup = PermutationGroup[perms];
generators = GroupGenerators[permGroup];

outOfOrderExample = {3, 1, 2, 4};
reversePerm = FindPermutation[outOfOrderExample, Sort@outOfOrderExample];
GroupElementQ[permGroup, reversePerm]
ge2word = GroupElementToWord[permGroup, reversePerm];
(** result: {-4, 3,-1} - e.g 3 means apply perm 3,
  while -4 means apply inverse of perm 4 **)

reversePermSequence = 
  If[Positive@#, Identity, InversePermutation][
     generators[[Abs[#]]]] & /@ ge2word;

Fold[Permute, outOfOrderExample, reversePermSequence]
(*result {1,2,3,4}*)
$\endgroup$
3
  • $\begingroup$ Thank you! I did not know what the function was called. To be clear, -4 even though inverse of perm 4, is the same as 4 because it is self inverse. Right? $\endgroup$
    – QuantumDot
    Oct 6 '20 at 21:45
  • $\begingroup$ @QuantumDot Yes the language of group theory and most modern algebra is needlessly byzantine. And yes, it just so happens that InversePermutation[perms[[4]]] is the same as perms[[4]]. $\endgroup$
    – flinty
    Oct 6 '20 at 21:48
  • $\begingroup$ I made some minor edits which uses the group generators instead of the original perms and fixes the order, since I noticed a bug when trying some different groups. I realize the generators are the same, but this is just so anybody passing by with a different set of perms finds this useful. $\endgroup$
    – flinty
    Oct 6 '20 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.