1
$\begingroup$

Let's have $K$ permutations $P_1$, $P_2$, ... $P_K$ of the same set $M$. For example $M$ can be the set of stickers on Rubik's cube and $P_1$, $P_2$, ... $P_K$ are allowed cube moves. The set of all permutations which can be created by repeated composing $P_1$, $P_2$, ... $P_K$ forms a permutation group $G$. The group operation is permutation composition. The group created this way with Rubik'cube moves is known under the name Rubik's Cube group.

I have two questions:

  1. Let's denote $N$ the cardinality of group $G$. How can I compute $N$?

  2. I would like to be able encode each permutation to natural number from $1$ to $N$.

Continuing the example I have given the first question is equivalent to asking number of reachable states of Rubik's cube. Which is well known.

Encoding Rubik's cube states to natural numbers is also quite straightforward. You just encode positions and orientations of all cubies except few information (like orientation of last edge and last corner, ...), which can be computed from the rest.

What is more general algorithm for doing this? I would like to be able to do this generally for any permutation group given set of permuations $P_1$, $P_2$, ... $P_K$ which "generate" the group.

Obviously some inefficient algorithms theoretically exist e.g. extensive search which tries all sequences of permutation compositions. This could be also used to assign a number to each permutation. But this procedure is extremely slow.

How can I do it faster? My intuition says that if it is possible to do this for Rubik's cube then it should be possible to compute this for other twisty puzzles or permutation groups. But how?

My third question is: Given a permutation $Q$ how can I decide if it is in group $G$ i.e. if it is equal to some composition of permutations $P_1$, $P_2$, ... $P_K$. Again finding whether a state of Rubick's cube is valid is simple. But how can I decide this more generally without searching the whole space?

$\endgroup$
  • $\begingroup$ See wikipedia: The cardinality of G is given by $|G|=43,252,003,274,489,856,000=2^{27}3^{14}5^37^211$. A proof is given in reference $[5]$. $\endgroup$ – Dietrich Burde Jul 28 '18 at 15:06
  • $\begingroup$ So you're looking for general algorithms that can answer those questions for subgroups of $S_n$ given by an arbitrary set of permutations, is that correct? $\endgroup$ – Henning Makholm Jul 28 '18 at 15:10
  • $\begingroup$ @HenningMakholm Yes, that is correct. $\endgroup$ – Bob Jul 28 '18 at 15:19
  • 1
    $\begingroup$ To compute the size of a group generated by some permutations, you can use the Schreier-Sims algorithm: en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm $\endgroup$ – Lord Shark the Unknown Jul 28 '18 at 15:24
  • $\begingroup$ @LordSharktheUnknown Great. I will look on that and that might be answer to first of the three questions I formulated. $\endgroup$ – Bob Jul 28 '18 at 15:27

Your Answer

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

Browse other questions tagged or ask your own question.