Rubiks Cube/Permutations - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:52:10Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:52, 9 October 2019
Line 422:		Line 422:
	To implement a program to turn a sequence of moves into a permutation, and factor the permutation into its component cycles, we utilized the NxNxN rubiks solver here: https://github.com/dwalton76/rubiks-cube-NxNxN-solver		To implement a program to turn a sequence of moves into a permutation, and factor the permutation into its component cycles, we utilized the NxNxN rubiks solver here: https://github.com/dwalton76/rubiks-cube-NxNxN-solver

	We also made modifications to implement some functionality not contained in the original cube object. Forked version is here: https://charlesreid1.com~~:3000~~/charlesreid1/rubiks-cube-nnn-solver		We also made modifications to implement some functionality not contained in the original cube object. Forked version is here: https://git.charlesreid1.com/charlesreid1/rubiks-cube-nnn-solver

	We have a main driver program to perform the factoring here: https://git.charlesreid1.com/charlesreid1/rubiks-cube-cycles		We have a main driver program to perform the factoring here: https://git.charlesreid1.com/charlesreid1/rubiks-cube-cycles

Admin: /* Code */

2019-04-21T18:35:14Z

Code

← Older revision		Revision as of 18:35, 21 April 2019
Line 424:		Line 424:
	We also made modifications to implement some functionality not contained in the original cube object. Forked version is here: https://charlesreid1.com:3000/charlesreid1/rubiks-cube-nnn-solver		We also made modifications to implement some functionality not contained in the original cube object. Forked version is here: https://charlesreid1.com:3000/charlesreid1/rubiks-cube-nnn-solver

	We have a main driver program to perform the factoring here: https://charlesreid1.com~~:3000~~/charlesreid1/rubiks-cube-cycles		We have a main driver program to perform the factoring here: https://git.charlesreid1.com/charlesreid1/rubiks-cube-cycles

	Let's run through the essential components of how we do this in code.		Let's run through the essential components of how we do this in code.
Line 1,059:		Line 1,059:
	return factors		return factors
	</pre>		</pre>




	=Flags=		=Flags=

Admin: /* Sequence R */

2019-04-21T18:33:54Z

Sequence R

← Older revision		Revision as of 18:33, 21 April 2019
Line 247:		Line 247:
	==Sequence R==		==Sequence R==

	Let's look at an example of applying this to a 4x4 Rubiks Revenge cube. We will consider the sequence "R" (turning the right face clockwise once).		Let's look at an example of applying this to a 4x4 [[Rubiks Revenge]] cube. We will consider the sequence "R" (turning the right face clockwise once).

	Start with the solved state:		Start with the solved state:

Admin: /* Writing a Permutation */

2019-03-17T18:10:46Z

Writing a Permutation

← Older revision		Revision as of 18:10, 17 March 2019
Line 16:		Line 16:
	==Writing a Permutation==		==Writing a Permutation==

	Knuth introduces the top-bottom notation for permutations, in which a particular permutation of a sequence of <math>n</math> integers is written by first writing each element of the sequence in increasing order on the top row, then writing the occurrence of each element in the order it occurs on the bottom row:		Knuth introduces the top-bottom notation for permutations, in which a particular permutation of a sequence of <math>n</math> integers is written by first writing each element of the sequence in increasing order on the top row, then writing the occurrence of each element in the order it occurs on the bottom row. For example, the permutation where each element is shifted by one would be written:

	<math>		<math>

Admin: /* Sequence R */

2018-01-25T19:47:43Z

Sequence R

@@ Line 264: / Line 264: @@
 <pre>
 Factors:
-(1)
+[36, 84, 77, 4]
-(2)
+[40, 88, 73, 8]
-(3)
+[44, 92, 69, 12]
-(36 84 77 4)
+[48, 96, 65, 16]
-(5)
+[61, 64, 52, 49]
-(6)
+[57, 63, 56, 50]
-(7)
+[53, 62, 60, 51]
-(40 88 73 8)
+[58, 59, 55, 54]
-(9)
+Independent Pieces: [1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 41, 42, 43, 45, 46, 47, 66, 67, 68, 70, 71, 72, 74, 75, 76, 78, 79, 80, 81, 82, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95]
-(10)
+Least common multiple: 4
 </pre>

Admin: /* Sequence U R U' R' */

2018-01-25T19:47:16Z

Sequence U R U' R'

@@ Line 364: / Line 364: @@
 <pre>
 Factors:
-(1)
+[77, 65, 96, 52, 64, 4]
-(2)
+[73, 15, 8]
-(3)
+[69, 14, 12]
-(77 65 96 52 64 4)
+[16, 20, 36, 33, 49, 13]
-(5)
+[50, 56, 34]
-(6)
+[51, 60, 35]
-(7)
+Independent Pieces: [1, 2, 3, 5, 6, 7, 9, 10, 11, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 53, 54, 55, 57, 58, 59, 61, 62, 63, 66, 67, 68, 70, 71, 72, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95]
-(73 15 8)
+Least common multiple: 6
 </pre>

Admin: /* Sequence U R */

2018-01-25T19:46:41Z

Sequence U R

← Older revision		Revision as of 19:46, 25 January 2018
Line 480:		Line 480:
	</pre>		</pre>

	This illustrates a special case that we did not see earlier: by indexing each of the four center faces with different integers, we have made the implicit assumption that the square faces are ''not'' interchangeable. This was necessary for corner and double-edge pieces, because orientation was important - double edge blue faces are not interchangeable, and the double edge with a blue face linked to a red face is different and distinct from a double edge with a blue face linked to an orange face.		However, the adventurous cuber will find, when actually carrying out this move sequence, that the order is in fact 105, and not 420.

			So what gives? Why is the predicted order 4 times larger than the one we actually see?

			This move sequence illustrates a special case that we did not see earlier: by indexing each of the four center faces with different integers, we have made the implicit assumption that the square faces are ''not'' interchangeable. This was necessary for corner and double-edge pieces, because orientation was important - double edge blue faces are not interchangeable, and the double edge with a blue face linked to a red face is different and distinct from a double edge with a blue face linked to an orange face.

	However, square faces are not linked to any other faces, so distinguishing between the NW and SE faces do not matter. But rather than complicate matters by changing our tuple representation, we can simply account for the fact that the squares are interchangeable.		However, square faces are not linked to any other faces, so distinguishing between the NW and SE faces do not matter. But rather than complicate matters by changing our tuple representation, we can simply account for the fact that the squares are interchangeable.

Admin: /* Sequence U R */

2018-01-25T19:45:43Z

Sequence U R

@@ Line 461: / Line 461: @@
 <pre>
 (13 9 5 1 14 10 6 2 15 11 7 3 48 44 40 36 33 34 35 84 21 22 23 24 25 26 27 28 29 30 31 32 61 57 53 49 37 38 39 88 41 42 43 92 45 46 47 96 16 66 67 68 62 58 54 50 63 59 55 51 64 60 56 52 17 18 19 20 12 70 71 72 8 74 75 76 4 78 79 80 81 82 83 77 85 86 87 73 89 90 91 69 93 94 95 65)
 </pre>

Admin: /* Sequence R */

2018-01-25T19:21:32Z

Sequence R

← Older revision		Revision as of 19:21, 25 January 2018
Line 338:		Line 338:
	(95)		(95)
	</pre>		</pre>

			The largest set of faces that are exchanged is 4, and the smallest is 1. No other groups of faces being exchanged have any other sizes. This means that if we apply the sequence 4 times, each of those groups of faces being interchanged will have returned to their original state.

	This tells us what we already knew: that if we apply the sequence "R", it rotates groups of pieces in a sequence of 4 moves each, so overall the order of this permutation is 4 - if we apply the sequence R to a solved 4x4 Rubik's Revenge cube 4 times, the cube will return to the solved state.		This tells us what we already knew: that if we apply the sequence "R", it rotates groups of pieces in a sequence of 4 moves each, so overall the order of this permutation is 4 - if we apply the sequence R to a solved 4x4 Rubik's Revenge cube 4 times, the cube will return to the solved state.

			To formalize this, if we have cycles with arbitrary lengths, we must apply the sequence a number of times equal to the least common multiple of each factor's size. (For example, if we had a cycle of length 3 above, the cycle order would have been 12 - because the sequence must be applied 12 times before the 4-cycle face exchanges "sync up" with the 3-cycle face exchanges.)

	==Sequence U R U' R'==		==Sequence U R U' R'==

Admin: /* An Example */

2018-01-20T09:16:50Z

An Example

← Older revision		Revision as of 09:16, 20 January 2018
Line 115:		Line 115:
	===Assembling Factors===		===Assembling Factors===

	We can ~~assemble~~ each factor one at a time using the following algorithm:		We can extract each factor one at a time using the following algorithm:

	Start by supposing that the first factor <math>\alpha</math> contains the first symbol <math>a</math>. If this assumption is true, then <math>\alpha</math> must map <math>a</math> to the same thing that the final permutation maps <math>a</math> to, namely, the first column of <math>\pi</math>, which is the combination <math>\begin{smallmatrix}		Start by supposing that the first factor <math>\alpha</math> contains the first symbol <math>a</math>. If this assumption is true, then <math>\alpha</math> must map <math>a</math> to the same thing that the final permutation maps <math>a</math> to, namely, the first column of <math>\pi</math>, which is the combination <math>\begin{smallmatrix}
Line 242:		Line 242:

	(Note: had we initially assumed <math>\alpha</math> contained b instead of a, we would end up starting by pulling out a different factor, but we would ultimately end up with the same set of four factors.)		(Note: had we initially assumed <math>\alpha</math> contained b instead of a, we would end up starting by pulling out a different factor, but we would ultimately end up with the same set of four factors.)


	=Application to Rubiks Cube=		=Application to Rubiks Cube=