Ravi
Member
A year or two ago, I set out to calculate with pencil and paper the set of all possible orders* of Rubik's Cube positions, combined with the number of positions with each order. The calculation isn't horribly difficult from a theoretical standpoint (SPOILER: details listed below), but my patience didn't last, and I put the question aside.
Today, I tried a similar calculation with a more modest goal: finding only the possible orders. I believe I have succeeded in this. I started by restricting my view to only edges and only corners respectively. The possible cycle structures of edges (or corners) correspond exactly to the partitions of 12 (or 8). I listed all of these partitions in "even permutation" and "odd permutation" columns. Then I found the order of each permutation, noting that for all permutations except a single 12-cycle of edges (or 8-cycle of corners) it is possible for some cycles to be off by a flipped edge (or twisted corner), and therefore that the orders of those permutations can be multiplied by 2 for edges (or 3 for corners). I then tabulated all possible orders for four categories:
ee (edges, even permutation): {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 30, 35, 40, 42, 60}
eo (edges, odd permutation): {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 28, 30, 36, 40, 42, 48, 56, 60, 84, 120}
ce (corners, even permutation): {1, 2, 3, 4, 5, 6, 7, 9, 12, 15, 18, 21, 45}
co (corners, odd permutation): {2, 4, 6, 8, 10, 12, 18, 30, 36}
Since ee only coexists with ce and eo with co, I had Mathematica list all LCMs of an ee order and a ce, as well as LCMs of an eo with a co. Combining the two lists, I obtained the following:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 30, 33, 35, 36, 40, 42, 44, 45, 48, 55, 56, 60, 63, 66, 70, 72, 77, 80, 84, 90, 99, 105, 110, 112, 120, 126, 132, 140, 144, 154, 165, 168, 180, 198, 210, 231, 240, 252, 280, 315, 330, 336, 360, 420, 462, 495, 504, 630, 720, 840, 990, 1260.
These are all possible orders of Rubik's Cube positions. Their frequencies could be found by attaching to each ee/eo/ce/co its frequency (it's not too hard to find the probability of having a "bad" cycle) and carrying these over to the LCMs at the end--this last stage is where I gave up last time.
Feel free to verify my work, or to construct the full table of frequencies. I'd be glad to check your work if you can get some results.
EDIT: This calculation may well have been done before, but I haven't seen it. I googled and oeis-ed the numbers without any results. I once did, however, see a web page listing some short algs for 3x3, 4x4, and 5x5 with given orders--I can't find that page now, and I don't remember who made it, but I remember being so disappointed at the absence of order 11 that I decided to look for the shortest possible pure 11-cycle. (The best I got was L B' F2 L2 U R U L R B2 D R2 B D'.)
*"order" = number of times one must repeat an algorithm before it produces the identity. Here I am abusing notation a little by equating an algorithm with the position it generates when applied to a solved cube.
Today, I tried a similar calculation with a more modest goal: finding only the possible orders. I believe I have succeeded in this. I started by restricting my view to only edges and only corners respectively. The possible cycle structures of edges (or corners) correspond exactly to the partitions of 12 (or 8). I listed all of these partitions in "even permutation" and "odd permutation" columns. Then I found the order of each permutation, noting that for all permutations except a single 12-cycle of edges (or 8-cycle of corners) it is possible for some cycles to be off by a flipped edge (or twisted corner), and therefore that the orders of those permutations can be multiplied by 2 for edges (or 3 for corners). I then tabulated all possible orders for four categories:
ee (edges, even permutation): {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 30, 35, 40, 42, 60}
eo (edges, odd permutation): {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 28, 30, 36, 40, 42, 48, 56, 60, 84, 120}
ce (corners, even permutation): {1, 2, 3, 4, 5, 6, 7, 9, 12, 15, 18, 21, 45}
co (corners, odd permutation): {2, 4, 6, 8, 10, 12, 18, 30, 36}
Since ee only coexists with ce and eo with co, I had Mathematica list all LCMs of an ee order and a ce, as well as LCMs of an eo with a co. Combining the two lists, I obtained the following:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 30, 33, 35, 36, 40, 42, 44, 45, 48, 55, 56, 60, 63, 66, 70, 72, 77, 80, 84, 90, 99, 105, 110, 112, 120, 126, 132, 140, 144, 154, 165, 168, 180, 198, 210, 231, 240, 252, 280, 315, 330, 336, 360, 420, 462, 495, 504, 630, 720, 840, 990, 1260.
These are all possible orders of Rubik's Cube positions. Their frequencies could be found by attaching to each ee/eo/ce/co its frequency (it's not too hard to find the probability of having a "bad" cycle) and carrying these over to the LCMs at the end--this last stage is where I gave up last time.
Feel free to verify my work, or to construct the full table of frequencies. I'd be glad to check your work if you can get some results.
EDIT: This calculation may well have been done before, but I haven't seen it. I googled and oeis-ed the numbers without any results. I once did, however, see a web page listing some short algs for 3x3, 4x4, and 5x5 with given orders--I can't find that page now, and I don't remember who made it, but I remember being so disappointed at the absence of order 11 that I decided to look for the shortest possible pure 11-cycle. (The best I got was L B' F2 L2 U R U L R B2 D R2 B D'.)
*"order" = number of times one must repeat an algorithm before it produces the identity. Here I am abusing notation a little by equating an algorithm with the position it generates when applied to a solved cube.
Last edited: