-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi GAP Forum,
I'm a relatively new user of GAP and this is my first Forum post. I'm having a great time exploring various permutation puzzle groups so thank you very much to all of the developers that have helped to make such great software! A common problem that comes up on certain permutation puzzles has to do with "extra" symmetry of certain positions when the whole puzzle is reoriented in space. When this happens simple combinatoric counting arguments only produce an approximate number of distinct states. This doesn't happen for the 3x3x3 Rubik's Cube because the 6 face centers always provide a reference. My trouble is when you don't have a reference and certain positions have extra symmetry so they look identical from more than one orientation of the puzzle. If you'd like to see an image of a puzzle where this happens, I've asked about this problem (with images) at http://math.stackexchange.com/q/1822752/132892 So let me be specific. I have a 2x2x2 Rubik's Cube defined by the following 3 generators: # Turn U face TU := (1, 2, 3, 4)(5, 7, 9, 11)(6, 8, 10, 12); # Rotate whole puzzle around U face RU := (1, 2, 3, 4)(5, 7, 9, 11)(6, 8, 10, 12) (13, 15, 17, 19)(14, 16, 18, 20)(21, 22, 23, 24); # Rotate whole puzzle around L face RL := (5, 6, 14, 13)(1, 7, 22, 20)(2, 15, 21, 12) (4, 8, 23, 19)(3, 16, 24, 11)(10, 9, 17, 18); I can make a group using these generators and also a group using just the two orientation generators: # The whole 2x2x2 cube group custom222 := Group([TU, RU, RL]); # The 24 orientations of a 2x2x2 custom222o := Group([RU, RL]); gap> Size(custom222o); 24 gap> Size(custom222) / 24; 3674160 The 3674160 number is the correct number of positions for a normal 2x2x2 Rubik's cube. I had to divide the number by 24 because the cube has 24 orientations and positions that are equivalent under orientation are counted as the same position. Trouble arises when I want to look at variations of this 2x2x2 where some stickers look identical. I have defined which stickers are identical this way: samecolors := [[1, 5, 12, 16, 17, 23],[3, 7, 10, 14, 19, 21], [2, 4, 6, 8, 9, 11, 13, 15, 18, 20, 22, 24]]; Now I'd like to know how many identical positions there are using this set of stickers. I can do that with a stabilizer using OnTuplesSets which will count how many configurations of the 2x2x2 permute stickers within each set of identical stickers. If I divide the size of the whole group by the size of the identical solutions group I should get the number of distinct positions: gap> (Size(custom222) / Size(Stabilizer(custom222, samecolors, OnTuplesSets))) / 24; 1701/2 Unfortunately 1701/2 isn't the right answer. It's not even a whole number. The problem is that some positions look identical in more than one orientation so Burnside's Lemma needs to be applied. I have already done this application of Burnside's Lemma by hand to get the correct answer of 893. The answer GAP gave of 850.5 wasn't that far away. One thing I need to know for Burnside's Lemma is all the symmetries of the cube. I can enumerate this by hand but GAP can also tell me it using the custom222o group: gap> List(ConjugacyClasses(custom222o), Size); [ 1, 6, 3, 8, 6 ] 1 is the identity so the cube isn't rotated at all 6 is the six 90-degree rotations about a cube face 3 is the three 180-degree rotations about a cube face 8 is the eight 120-degree rotations about a cube corner 6 is the six 180-degree rotations about a cube edge By hand I can calculate how many positions of the custom222 group fall into each of these conjugacy classes, sum them up, and divide by 24 to get the correct results of 983. I have also written a program to use iterative-deepening BFS to enumerate all positions and it confirms that 893 is indeed correct. But how do I get GAP to give me this number? I feel like I have all the pieces but I don't know how to put them together. If I can get it working for this simple case, that will allow me to tackle much more complicated puzzles for which a manual by-hand calculation just isn't possible. Thanks in advance for any guidance or pointers for how to handle this! Best regards, Brandon -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iEYEARECAAYFAld69doACgkQqaGPzAsl94KQ+QCeMHWG5rHLUwaKXO8jvCoV5nt2 fE0AoKqEvsi9hdB87DU5IBtMruzmBfVM =KoEP -----END PGP SIGNATURE----- _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum
