Mixing
Cardinality of permutation group
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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:
Let's denote $N$ the cardinality of group $G$. How can I compute $N$?
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?
abstract-algebra group-theory permutations symmetric-groups rubiks-cube
asked Jul 28 at 15:02
Bob
61
 |Â
show 5 more comments
up vote
1
down vote
favorite
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:
Let's denote $N$ the cardinality of group $G$. How can I compute $N$?
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?
abstract-algebra group-theory permutations symmetric-groups rubiks-cube
asked Jul 28 at 15:02
Bob
61
See wikipedia: The cardinality of G is given by $|G|=43,252,003,274,489,856,000=2^273^145^37^211$. A proof is given in reference $[5]$.
– Dietrich Burde
Jul 28 at 15:06
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?
– Henning Makholm
Jul 28 at 15:10
@HenningMakholm Yes, that is correct.
– Bob
Jul 28 at 15:19
1
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
– Lord Shark the Unknown
Jul 28 at 15:24
@LordSharktheUnknown Great. I will look on that and that might be answer to first of the three questions I formulated.
– Bob
Jul 28 at 15:27
 |Â
show 5 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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:
Let's denote $N$ the cardinality of group $G$. How can I compute $N$?
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?
abstract-algebra group-theory permutations symmetric-groups rubiks-cube
asked Jul 28 at 15:02
Bob
61
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:
Let's denote $N$ the cardinality of group $G$. How can I compute $N$?
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?
abstract-algebra group-theory permutations symmetric-groups rubiks-cube
asked Jul 28 at 15:02
Bob
61
asked Jul 28 at 15:02
Bob
61
asked Jul 28 at 15:02
Bob
61
asked Jul 28 at 15:02
Bob
61
61
See wikipedia: The cardinality of G is given by $|G|=43,252,003,274,489,856,000=2^273^145^37^211$. A proof is given in reference $[5]$.
– Dietrich Burde
Jul 28 at 15:06
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?
– Henning Makholm
Jul 28 at 15:10
@HenningMakholm Yes, that is correct.
– Bob
Jul 28 at 15:19
1
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
– Lord Shark the Unknown
Jul 28 at 15:24
@LordSharktheUnknown Great. I will look on that and that might be answer to first of the three questions I formulated.
– Bob
Jul 28 at 15:27
 |Â
show 5 more comments
See wikipedia: The cardinality of G is given by $|G|=43,252,003,274,489,856,000=2^273^145^37^211$. A proof is given in reference $[5]$.
– Dietrich Burde
Jul 28 at 15:06
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?
– Henning Makholm
Jul 28 at 15:10
@HenningMakholm Yes, that is correct.
– Bob
Jul 28 at 15:19
1
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
– Lord Shark the Unknown
Jul 28 at 15:24
@LordSharktheUnknown Great. I will look on that and that might be answer to first of the three questions I formulated.
– Bob
Jul 28 at 15:27
See wikipedia: The cardinality of G is given by $|G|=43,252,003,274,489,856,000=2^273^145^37^211$. A proof is given in reference $[5]$.
– Dietrich Burde
Jul 28 at 15:06
See wikipedia: The cardinality of G is given by $|G|=43,252,003,274,489,856,000=2^273^145^37^211$. A proof is given in reference $[5]$.
– Dietrich Burde
Jul 28 at 15:06
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?
– Henning Makholm
Jul 28 at 15:10
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?
– Henning Makholm
Jul 28 at 15:10
@HenningMakholm Yes, that is correct.
– Bob
Jul 28 at 15:19
@HenningMakholm Yes, that is correct.
– Bob
Jul 28 at 15:19
1
1
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
– Lord Shark the Unknown
Jul 28 at 15:24
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
– Lord Shark the Unknown
Jul 28 at 15:24
@LordSharktheUnknown Great. I will look on that and that might be answer to first of the three questions I formulated.
– Bob
Jul 28 at 15:27
@LordSharktheUnknown Great. I will look on that and that might be answer to first of the three questions I formulated.
– Bob
Jul 28 at 15:27
 |Â
show 5 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865312%2fcardinality-of-permutation-group%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
See wikipedia: The cardinality of G is given by $|G|=43,252,003,274,489,856,000=2^273^145^37^211$. A proof is given in reference $[5]$.
– Dietrich Burde
Jul 28 at 15:06
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?
– Henning Makholm
Jul 28 at 15:10
@HenningMakholm Yes, that is correct.
– Bob
Jul 28 at 15:19
1
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
– Lord Shark the Unknown
Jul 28 at 15:24
@LordSharktheUnknown Great. I will look on that and that might be answer to first of the three questions I formulated.
– Bob
Jul 28 at 15:27