charlesreid1.com research & teaching

Project Euler Problem 172

Posted in Mathematics

permalink

Table of Contents



Overview: Problem 172

How many 18-digit numbers \(n\) (without leading zeros) are there such that no digit occurs more than three times in \(n\)?

Link to Project Euler Problem 172

Background

Project Euler Problem 172 is your classic Project Euler problem: short, simple, and overwhelmingly complicated.

To nail this one, it's important to start simple - very simple. What I'll do is walk through the process of breaking this problem down to find and generalize the patterns needed to count permutations of digits.

First, in combinatorics problems it is important to think about what is changing, and how to count possible outcomes one piece at a time. Then the overall pieces can be combined to get the total count. In this case, we can think about a case for each digit: the case of 3 occurrences, the case of 2 occurrences, the case of 1 occurrence, and the case of 0 occurrences. Depending on the case, we limit our choices for later digits.

Let's start with a similar, but much simpler, problem: how do we construct a binary number with N digits and no more than m 0s and no more than m 1s?

In fact, let's make it even easier: how do we construct a 10 digit binary number with no more than 5 0's and no more than 5 1's?

The answer is, there is only ONE way to choose no more than 5 0's and no more than 5 1's to form a 10 digit number, and that's by having exactly 5 0's and 5 1's. Now that we know exactly how many of each digit we have, we can count the number of permutations of the number 0000011111 (the number of permutations).

Multiset Permutations

Note that multiset permutations are also discussed on the following wiki pages and blog posts:

If we are selecting from a group of \(N_1\) things of type A, \(N_2\) things of type B, and \(N_3\) things of type C to form a total of \(N\) things, this type of combinatorics problem is called a multiset permutation, and the total number of ways of arranging this set of 3 things is given by:

$$ \binom{N}{N_1, N_2, N_3} = \dfrac{N!}{N_1! N_2! N_3!} $$

In fact, this generalizes, for \(k\) classes of things we have a \(k\)-set permutation:

$$ \binom{N}{N_1, \dots, N_k} = \dfrac{N!}{N_1! \dots N_k!} $$

A Simple Problem (And Solution)

Back to the problem at hand: to count the number of ways of placing 5 0s and 5 1s to form a 10 digit number.

Once we place 5 digits into any of the 10 available slots, that fixes the locations of the remaining 5 digits. However, we still have to include two 5! values, to account for all possible duplicates if we exchanged all 5 of the 1s with one another, or all 5 of the 0s with one another. We use the expression:

$$ \binom{10}{5} = \dfrac{10!}{5! 5!} = 10 \times 9 \times 8 \times 7 \times 6 $$

A slightly More Complicated Problem

To solve a slightly more complicated problem: suppose we have to assemble a 10-digit binary number from no more than 6 0s and no more than 6 1s?

Now we have 3 possible cases of numbers of 0s:

4 0s: 0000111111 - and its permutations

5 0s: 0000011111 - and its permutations

6 0s: 0000001111 - and its permutations

For each of these cases, we can think of it as the "bucket" of 0s containing 4 0s (5 and 6 0s, respectively) and the "bucket" of 1s containing 6 1s (5 and 4 1s, respectively). We still have a number of permutations that we can form using this given number of 0s and 1s, given by a multiset permutation expression.

For each case, we have a multiset permutation expression that tells us how many permutations we can form from the given number of 0s and 1s:

$$ \binom{ N }{ N_0, N_1 } $$

So we have three possible outcomes, and the total number of arrangements is the sum of these three cases:

$$ N_{perms} = \binom{ 10 }{ 6, 4} + \binom{ 10 }{ 5, 5 } + \binom{ 10 }{ 6 , 4 } $$

Algorithm

We can generalize the process. Suppose we are forming a number of length N from a number of digits/classes \(k\) labeled from \(0 \dots k-1\), and each digit/class can only appear a maximum of \(m\) times.

The number of combinations that can be formed for a given \(N, k, m\) is given by the multiset permutation expression above. So the total number of permutations that can be formed is a sum of these multiset permutation expressions, over each possible combination of digits/classes into a number of length \(N\).

In computer science terms, we can think of this as a nested for loop or dynamic program; in mathematical terms, we can think of a sequence of summations whose limits depend on the variables in the other summations.

$$ \sum_{N_1} \sum_{N_2} \dots \sum_{N_k} \binom{N}{N_0, N_1, N_2, \dots, N_{k-1}} $$

where the limits of the summations are given by:

$$ N_1 = \min \left(N - (k-1) m, 0 \right) \dots m $$
$$ N_2 = \min \left( N - N_1 - (k-2) m, 0 \right) \dots m $$

etc...

$$ N_{k-1} = \min \left( N - N_1 - N_2 - \dots - N_{k-2}, 0 \right) \dots m $$

these all fix the number of zeros N_0:

$$ N_0 = N - N_1 - N_2 - N_3 - \dots - N_k $$

Notice that we ignore N_0 in the list of summations, because fixing the number of the first k-1 digits/classes (1s, 2s, 3s, ..., (k-1)s) will fix the number of 0s. Alternatively, we could count 0s and include a summation over \(N_0\), and eliminate the last summation over \(k-1\).

However, the multiset permutation expression includes ALL of the N's, from \(N_0\) to \(N_{k-1}\), since the choice of each variable leads to additional permutations.

Also note that any algorithm implementing this procedure can save time by checking if, for the preceding combinations of \(N\), we have already reached the maximum possible digits that can be selected. (Alternatively, we could write the upper limit of the summations as expressions depending on the prior values of \(N_i\), but we'll keep it simple.)

Ignoring Numbers Starting with Zero

We have one last hurdle remaining, and that is how to ignore numbers that start with 0.

If we think about the problem as selecting the number of times each digit is repeated, then assembling that selection into all possible permutations, fixing the first digit as 0 is equivalent to removing one from the total length of the number that must be assembled, and removing one from the possible 0s that will go in the final number. Thus, if we are assembling an N digit number from \(N_0\) 0s, \(N_1\) 1s, \(N_2\) 2s, \(N_3\) 3s, on up to \(N_9\) 9s, then the total number of permutations is given by:

$$ \binom{ N }{N_0, N_1, \dots, N_9} $$

If we fix the first digit as 0, the remaining number of permutations is given by:

$$ \binom{N-1}{ N_0-1, N_1, \dots, N_9 } $$

Therefore, the number of permutations, excluding those beginning with 0, is written:

$$ \binom{ N }{N_0, N_1, \dots, N_9} - \binom{N-1}{ N_0-1, N_1, \dots, N_9 } $$

Also, it is important to note that if N_0 = 0 to begin with, there are no possible ways of assembling numbers that begin with 0 because there are no 0s in the number, so the second term becomes 0:

$$ \binom{ N }{0, N_1, \dots, N_9} - 0 $$

Code

Test Cases

Test Case 1

Assemble two digits \(\{0,1\}\) into a 10-digit number, if each digit \(\{0,1\}\) can occur up to 5 times.

In this case, we know that 0 and 1 must occur exactly 5 times each. Now we are asking how we can assemble two sets of 5 things into 10 slots. This is a multiset permutation problem:

$$ \binom{10}{5,5} = \dfrac{10!}{5! \cdot 5!} = \dfrac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 252 $$

But wait! We also want to exclude numbers starting with 0, so we actually have:

$$ \binom{10}{5, 5} - \binom{9}{4, 5} = 126 $$

which is half of 252 - exactly what we would expect.

Test Case 2

Assemble three digits \(\{[0, 1, 2\}\) into a 6-digit number, if each digit \(\{0, 1, 2\}\) can occur up to 3 times. No number should start with 0.

In the prior case, we had one outcome of number of 0s and 1s, but in this case, we have a larger number of outcomes that we might see.

Evaluating the expressions for the limits of \(N_i\), we get:

$$ \sum_{N_0 = 0}^{3} \sum_{N_1 = \max(0, 3 - N_0) }^{3} \binom{6}{N_0, N_1, (N-N_0-N_1)} $$

where \(N_2 = N - N_0 - N_1\). Written out, this becomes the total number of possible 6-digit numbers,

$$ a = \binom{6}{0,3,3} + \binom{6}{1,2,3} + \binom{6}{1,3,2} + \binom{6}{2,1,3} + \binom{6}{2,2,2} + \\ \binom{6}{2,3,1} + \binom{6}{3,0,3} + \binom{6}{3,1,2} + \binom{6}{3,2,1} + \binom{6}{3,3,0} $$

minus the number of 6-digit numbers starting with 0:

$$ b = 0 + \binom{5}{0,2,3} + \binom{5}{0,3,2} + \binom{5}{1,1,3} + \binom{5}{1,2,2} + \\ \binom{5}{1,3,1} + \binom{5}{2,0,3} + \binom{5}{2,1,2} + \binom{5}{2,2,1} + \binom{5}{2,3,0} $$

Let \(a\) be the first expression and \(b\) be the second expression; then the total is:

In [40]: np.sum(a)
Out[40]: 510.0

In [41]: np.sum(b)
Out[41]: 170.0

In [42]: np.sum(a) - np.sum(b)
Out[42]: 340.0
$$ a - b = 340 $$

Recursion

The essence of this problem is a nested for loop - but because we have 9 digits to deal with, a 9-level nested for loop would be a big headache and would not generalize well.

Instead, we can write a recursive method that is called for each of the \(k\) (9) digits being selected to compose the final \(N\)- (18-) digit number.

The recursive method looks something like this:

global variable solution_count
global variable m
global variable N

def recursive_method( n_tuple, n) {
    if(n==9) {
        compute multiset permutation combinations
        increment global solutions total
        need N, N0, N1, N2, etc.
    } else {
        assemble choices for N_i
        for(choice in choices) {
            set N_i to choice
            call recursive_method()
            unset N_i
        }
    }
}

Pseudocode

Computing the number of possible integers n that meet the specified criteria thus boils down to a long sequence of nested summations (nested loops).

The problem is posed for \(N = 18, k = 10, m = 3\). For this case, the final expression for the total number of permutations is:

$$ \sum_{N_1} \sum_{N_2} \sum_{N_3} \sum_{N_4} \sum_{N_5} \sum_{N_6} \sum_{N_7} \sum_{N_8} \sum_{N_9} \binom{N}{N_0, N_1, N_2, \dots, N_9} - \binom{N-1}{N_0-1, N_1, N_2, \dots, N_9} $$

where the limits of summation are given by:

$$ N_1 = \max \left( N - (10-1) m, 0 \right) \dots m $$
$$ N_2 = \max \left( N - N_1 - (10-2) m, 0 \right) \dots m $$
$$ N_3 = \max \left( N - N_1 - N_2 - (10-3) m, 0 \right) \dots m $$
$$ N_4 = \max \left( N - N_1 - N_2 - N_3 - (10-4) m, 0 \right) \dots m $$

etc...

$$ N_9 = \max \left( N - N_1 - N_2 - \dots - N_7 - N_8, 0 \right) \dots m $$

and from these, \(N_0\) is determined by:

$$ N_0 = N - N_1 - N_2 - \dots - N_8 - N_9 $$

Python Code

Link to Problem 172 Python Code at git.charlesreid1.com

To implement the solution to Problem 172 in Python, we used recursion, as mentioned above. THe only tricky part of implementing this recursive method was the usual challenge with recursive methods: keeping track of the total number of solutions found via a global variable.

To do this in Python, we declare a variable outside the scope of a given function, and we use that variable as a global variable by declaring it with the global keyword.

import numpy as np

# Real problem:
k = 10
m = 3
N = 18


solution_count = 0
factorials = {}

Now we have a main() driver method to call the recursive method:

def main():
    global solution_count
    n_tuple = [None,]*k
    recursive_method(n_tuple,1)
    print("Total number of permutations:")
    print("%d"%(solution_count))

We have the recursive backtracking method that constructs all combinations of \(k\) digits into \(N\)-digit numbers:

def recursive_method( n_tuple, ni ):
    """
    Use recursive backtracking to form all possible 
    combinations of k digits into N-digit numbers 
    such that the number of digits is m or less.

    (n_tuple is actually a list.)

    ni = current class step 1..(k-1)
    n_tuple = list of number of digits for each class 0 through k
    """
    global solution_count, k, m, N
    if(ni==k):

        # N_1 through N_(k-1) have been set,
        # now it is time to set N_0:
        # N_0 = N - N_1 - N_2 - N_3 - .. - N_{k-1}
        sum_N = np.sum([n_tuple[j] for j in range(1,k)])
        n_tuple[0] = max(0, N-sum_N)

        # Compute multiset permutation
        solution_count += multiset(N,n_tuple) - multiset_0(N,n_tuple)

        return

    else:

        # Problem: we are not stopping 
        # when the sum of digits chosen
        # is greater than N

        # Assemble the minimum and maximum limits for N_i:
        # (Everything up to ni-1 should be defined, no TypeErrors due to None)
        sum_N = np.sum([n_tuple[j] for j in range(1,ni)])
        ktm = (k - ni)*m
        expr = N - sum_N - ktm
        minn = int(max( 0, expr ))

        # Note: previously this was just maxx=m.
        # This required a check around each call to
        # recursive_method to see if the sum of n_tuple
        # was already maxed out. Now we just do it here.
        maxx = min(m, N-sum_N)

        for N_i in range(minn,maxx+1):

                # Set
                n_tuple[ni] = N_i

                # Explore
                recursive_method(n_tuple, ni+1)

                # Unset
                n_tuple[ni] = None

        return

We have a multiset() method that evaluates the multiset permutation count formula:

$$ \binom{N}{N_1, \dots, N_k} = \dfrac{N!}{N_1! \dots N_k!} $$
def multiset(N, n_tuple):
    """
    Number of multiset permutations
    """
    r = factorial(N)/(np.product([factorial(j) for j in n_tuple]))
    return r


def multiset_0(N, n_tuple):
    """
    Number of multiset permutations that start with 0
    """
    if(n_tuple[0]>0):
        r = factorial(N-1)/(np.product([factorial(j-1) if(i==0) else factorial(j) for i,j in enumerate(n_tuple)]))
        return r
    else:
        return 0

And finally, we have a factorial() method:

def factorial(n):
    """
    Factorial utility
    """
    if(n<0):
        raise Exception("Error: negative factorials not possible")
    if(n==1 or n==0):
        return 1
    else:
        return n*factorial(n-1)

At the bottom of the file, we ensure that the driver is run when the funtion is run directly through Python:

if __name__=="__main__":
    main()

Final Answer

Setting the correct parameters should result in the following result:

$$ P = 227,485,267,000,992,000 $$

Tags:    computer science    mathematics    factors    sequences    euler    project euler   

4x4 Rubik's Cube: Part 4: Sequence Order

Posted in Rubiks Cube

permalink

This is Part 4 of a 4-part blog post on the mathematics of the 4x4 Rubik's Cube, its relation to algorithms, and some curious properties of Rubik's Cubes.

See Part 1 of this blog post here: Part 1: Representations

See Part 2 of this blog post here: Part 2: Permutations

See Part 3 of this blog post here: Part 3: Factoring Permutations

You are currently reading Part 4 of this blog post: Part 4: Sequence Order

Table of Contents




Introduction

Order of a Sequence

As a reminder of our overarching goal: starting with a 4x4 Rubik's Revenge cube, an arbitrary sequence of moves will scramble the faces of the cube; but if that move sequence is repeatedly applied, eventually the cube will return to its solved state.

The simplest example is rotating a single face: after applying the rotation move four times to any face of a solved cube, the cube will return back to the solved state.

This is also true of more complicated move sequences, such as U R U' R', which returns the cube back to its original state after 6 applications, or the move sequence U R, which must be applied 105 times before the cube returns back to its original solved state.

Our goal is to predict this number: given a move sequence, how many times must that move sequence be applied to a solved cube to return the cube back to its solved state?

This number is called the order of a sequence.

What We Have Covered So Far

In prior posts, we have covered a number of key topics that this post will synthesize.

We started Part 1 by discussing ways of representing the Rubik's Revenge cube, and we settled on a 96-tuple representation indicating which faces had moved to what locations.

That led us to Part 2, in which we discussed the two-row notation for the 96-tuple representing the cube, and demonstrated the utility of this representation by showing how moves and move sequences would lead to permutations that could be written as 96-tuples using the two-row notation.

In Part 3, we covered some key theoretical results following Donald Knuth's Art of Computer Programming which allowed us to develop a permutation algebra to describe the effects moves have on the cube. We concluded the previous post with an algorithm for factoring permutations into their intercalation products, and hinted that these permutation factors were central

Factoring Rubik's Cube Permutations

Factoring Permutations: A Review

In Part 3 of this series of blog posts, we looked at an example multiset permutation of characters. Here it is written using the two-row notation:

$$ \pi = \bigl(\begin{smallmatrix} a & a & b & b & b & b & b & c & c & c & d & d & d & d & d \\ d & b & c & b & c & a & c & d & a & d & d & b & b & b & d \end{smallmatrix}\bigr) $$

We covered a technique for factoring this permutation into independent cycles of faces,

$$ \pi = \alpha \top \beta \top \dots \top \gamma $$

and shared Python code to perform this operation. The resulting factored permutation was:

$$ \pi = \bigl( \begin{smallmatrix} a & d & d & b & c & d & b & b & c \\ d & d & b & c & d & b & b & c & a \end{smallmatrix} \bigr) \top \bigl( \begin{smallmatrix} a & b \\ b & a \end{smallmatrix} \bigr) \top \bigl( \begin{smallmatrix} b & c & d \\ c & d & b \end{smallmatrix} \bigr) \top \bigl( \begin{smallmatrix} d \\ d \end{smallmatrix} \bigr) $$

Factoring Rubik's Cube Permutations

To factor a Rubik's Cube permutation, we apply Algorithm A from the prior post to the two-row 96-tuple representation of the Rubik's Cube after it has had the move sequence applied once.

(Note that we only need to apply the sequence to the cube once, even if the order of that sequence is in the tens of thousands.)

Let's look at a few move sequences for some examples:

Computing the Order of Sequence R

We begin with the solved state, and apply the move R to the cube. The result is the two-line representation:

(01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96)
(01 02 03 36 05 06 07 40 09 10 11 44 13 14 15 48 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 84 37 38 39 88 41 42 43 92 45 46 47 96 61 57 53 49 62 58 54 50 63 59 55 51 64 60 56 52 16 66 67 68 12 70 71 72 08 74 75 76 04 78 79 80 81 82 83 77 85 86 87 73 89 90 91 69 93 94 95 65)

Now, we can carry out the Algorithm A procedure on this two-row representation. When we do that, we will find that there are a large number of one-element independent factors; these are the faces that do not move during the move sequence R.

Here is a list of factors that are found by Algorithm A:

Factor sizes: {1, 4}
Factors:
[36, 84, 77, 4]
[40, 88, 73, 8]
[44, 92, 69, 12]
[48, 96, 65, 16]
[61, 64, 52, 49]
[57, 63, 56, 50]
[53, 62, 60, 51]
[58, 59, 55, 54]
Independent Faces: [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]
Least common multiple: 4

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.

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.)

Let's look at a slightly more complicated move sequence to illustrate this point.

Computing the Order of Sequence U R U' R'

As before, we begin by applying the move sequence once to a solved cube to generate the two-row n-tuple representation:

(01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96)
(01 02 03 77 05 06 07 73 09 10 11 69 16 12 08 20 17 18 19 36 21 22 23 24 25 26 27 28 29 30 31 32 49 50 51 33 37 38 39 40 41 42 43 44 45 46 47 48 13 56 60 64 53 54 55 34 57 58 59 35 61 62 63 04 96 66 67 68 14 70 71 72 15 74 75 76 65 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 52)

Next, we factor this permutation using Algorithm A:

Factor sizes: {1, 3, 6}
Factors:
[77, 65, 96, 52, 64, 4]
[73, 15, 8]
[69, 14, 12]
[16, 20, 36, 33, 49, 13]
[50, 56, 34]
[51, 60, 35]
Independent Faces: [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]
Least common multiple: 6

This time, we get a couple of cycles with different lengths. We have four cycles of length 3, and two cycles of length 6, plus many cycles of length 1 (the unpermuted faces).

The LCM of 3 and 6 is 6, so the overall order of the move sequence U R U' R' is 6.

Computing the Order of Sequence U R

The last sequence we'll look at is the move sequence UR.

This particular permutation represents an interesting corner case: in Part 1 of this post, when we came up with our tuple representation for the cube, we treated each face as being non-interchangeable, by giving each face a unique number. This means that, for example, we cannot swap two arbitrary red faces, since they are attached to other faces via a double edge or a corner piece.

This assumption does not hold for faces in the center of the cube. Because center faces are not attached to any other faces (mechanically speaking), the four distinct integers representing four colored faces can actually be interchanged.

This plays out with the sequence U R as follows:

We start with the two-line representation of the n-tuple:

(01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96)
(13 09 05 01 14 10 06 02 15 11 07 03 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 08 74 75 76 04 78 79 80 81 82 83 77 85 86 87 73 89 90 91 69 93 94 95 65)

We can factor this tuple as follows:

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

However, the adventurous cuber will find, when actually carrying out this move sequence, that the order is in fact 105, and not 420.

The reason the predicted cube order is 4 times larger than expected is because, after 105 applications of the move sequence, the cube has not actually returned to its original state, but the only remaining faces that are scrambled are center faces, which are in fact interchangeable.

Note this group of 4 faces that are permuted:

[10, 11, 7, 6]

These are the four center squares from the U face. If we exclude this group (treating 10, 11, 7, and 6 as perfectly interchangeable), the length of all factors no longer contains 4:

Factor sizes: {1, 3, 7, 15}

Including the 4, we had

LCM(1,3,4,7,15) = 420

but excluding the 4, we get:

LCM(1,3,7,15) = 105

Systematically, we can search for any groups that contain only faces from the center, and treat 1 such group of length n as n groups of length 1 (not contributing to the order of the move sequence).

This provides an interesting contrast between the 4x4 Rubik's Revenge cube, in which any center faces may be interchanged with any other center faces, and the 3x3 Rubik's Cube, in which the center faces always remain fixed in relation to one another.

Computing the Order of Sequence Uw Rw

We mentioned in Part 1 that the move notation Uw or Dw indicates a quarter clockwise turn of two layers of a face, not one. We can write the permutation that results from the move sequence Uw Rw as:

(01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96)
(13 09 05 01 14 10 06 02 47 43 39 35 48 44 40 36 33 34 83 84 37 38 87 88 25 26 27 28 29 30 31 32 61 57 53 49 62 58 54 50 41 42 91 92 45 46 95 96 16 15 67 68 12 11 71 72 63 59 55 51 64 60 56 52 17 18 19 20 21 22 23 24 08 07 75 76 04 03 79 80 81 82 78 77 85 86 74 73 89 90 70 69 93 94 66 65)

Factoring this permutation, we get:

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

Several groups of 3 faces and of 15 faces, respectively, are permuted, giving an LCM of 15. Thus, the order of move sequence Uw Rw is 15.

We'll look at the factoring of one last sequence: U Rw.

Computing the Order of Sequence U Rw

Here is the permutation representing the permutation resulting from the sequence U Rw:

(01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96)
(13 09 05 01 14 10 06 02 47 43 39 35 48 44 40 36 33 34 83 84 21 22 23 24 25 26 27 28 29 30 31 32 61 57 53 49 37 38 87 88 41 42 91 92 45 46 95 96 16 15 67 68 62 58 54 50 63 59 55 51 64 60 56 52 17 18 19 20 12 11 71 72 08 07 75 76 04 03 79 80 81 82 78 77 85 86 74 73 89 90 70 69 93 94 66 65)

Factoring this permutation, we get:

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

The order of the move sequence U Rw is 240.

Code

The code that forms the permutation tuple for a given move sequence and performs the factoring of that tuple is in sequence_order.py.

The sequence_order.py file utilizes the dwalton76/rubiks-cube-NxNxN-solver library from Github to apply the move sequence once to a cube to determine the resulting permutation tuple. It then factors this tuple into products and finds the LCM of their lengths.

The code in sequence_order.py is grouped into functions, with the key funtion being factor_permutation(top, bottom), which takes the top and bottom rows of the two-row representation of a move sequence's permutation.

The method then performs the factoring procedure covered in Part 3.

Here is the body of the method:

def factor_permutation(perm_top,perm_bot):
    """
    Factor a permutation into its lowest terms
    """
    MAX = 96

    # Need a way to also mark them as used... bit vector
    used_vector = [0,]*len(perm_top)

    i = 0
    start = perm_top[0]
    used_vector[0] = 1
    factors = []

    # If we still have values to pick out:
    while(0 in used_vector):

        factor = []

        while(True):
            used_vector[i] = 1
            leader = perm_top[i]
            follower = perm_bot[i]

            i = perm_top.index(follower)
            while(used_vector[i]==1):
                i += 1
                if(i>=MAX):
                    break

            if(i>=MAX):
                break
            elif(follower==start):
                break
            else:
                factor.append(follower)

        # add start to end
        factor.append(start)

        factors.append(factor)
        try:
            #import pdb; pdb.set_trace()
            i = used_vector.index(0)
            start = perm_top[i]
        except ValueError:
            break

    return factors

This was called by the method applying move sequences to the Rubik's Cube to obtain the two-row permutation corresponding to the move sequence of interest.

Project Conclusions

In addition to being interesting, this project led to some deep insights into the workings of the Rubik's Cube and ways to think about move sequences.

More than that, the Rubik's Cube is a toy that provides real insight into combinatorics and group theory. The concept of order, and the process of thinking through different representations of the cube and their consequences for the implemetation of the final algorithm, provide good practice for problems in other, related domains.

This project began with a simple question. While playing with the Rubik's Cube, we discovered this property of cycles (it is actually difficult to miss, even when learning the beginner method, as many of the move sequences involved in the beginner method have small orders, so it is easy to see them repeat.) The question we set out to answer was, given an arbitrary sequence, can we determine the order of that sequence?

The key to answering this question ultimately lies in the representation of the permutations; the right representation makes finding the order possible. but it took some trial and error with different representations before discovering the right approach.

To anyone who has played with the Rubik's Cube before, it seems natural that there would be some way to represent moves applied to the cube in some kind of algebraic terms. The intercalation product was the key concept for developing a permutation algebra. Knuth's Algorithm A was the key concept for factoring permutations into their respective independent cycles.

Once an algorithm to factor permutations was developed, the rest was a straightforward calculation of the LCM of the lengths of each factor.

The project was computationally challenging; recursion was required to implement Algorithm A, the Rubik's Cube solver had to be modified, and there were many bugs along the way.

The procedure we used here can be applied to other problems. Our procedure was:

  • Find a proper, convenient representation for the system state
  • Break down the variations of the system into simple cases or steps
  • Move away from the specific system, and keep the approach mathematially general. This is by far the the most important step!
  • Study the literature and solutions to problems, to become familiar with different ways of representing a problem. Different problems lend themselves well to different representations, so the more familiar you are with different representations, the more problems you'll be able to tackle.
  • The only way to get familiar with different problem-solving approaches is through practice. It helps to start with easier problems, both because you can score some quick points and feel more confident, and also because combinatorics and group theory problems often tend to appear simple, but deceptively so. The devil is in the details.

References

  1. "Rubik's Cube". Charlesreid1.com wiki, Charles Reid. Edited 25 January 2017. Accessed 25 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube>

  2. "Rubik's Revenge". Charlesreid1.com wiki, Charles Reid. Edited 25 January 2017. Accessed 25 January 2017. <https://charlesreid1.com/wiki/Rubiks_Revenge>

  3. "Rubik's Cube/Tuple". Charlesreid1.com wiki, Charles Reid. Edited 25 January 2017. Accessed 25 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Tuple>

  4. "Rubik's Cube/Permutations". Charlesreid1.com wiki, Charles Reid. Edited 25 January 2017. Accessed 25 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Permutations>

  5. "Github - dwalton76/rubiks-cube-NxNxN-solver". dwalton76, Github Repository, Github Inc. Accessed 11 January 2017. <https://github.com/dwalton76/rubiks-cube-NxNxN-solver>

  6. "Rubik's Cube NxNxN Solver". Git repository, git.charlesreid1.com. Charles Reid. Updated 25 January 2017. <https://git.charlesreid1.com/charlesreid1/rubiks-cube-nnn-solver>

  7. "Rubiks Cube Cycles". Git repository, git.charlesreid1.com. Charles Reid. Updated 25 January 2017. <https://git.charlesreid1.com/charlesreid1/rubiks-cube-cycles>

Appendix

That concludes our discussion of computing the order of move sequences on a Rubik's Cube. There are many move sequences, and many orders, ranging from 1 or 2 up to nearly 100,000. We plan to assemble a web site to help readers explore some move sequences and their orders - so check back soon...

Tags:    rubiks cube    combinatorics    permutations    python    puzzles    art of computer programming    knuth   

4x4 Rubik's Cube: Part 3: Factoring Permutations

Posted in Rubiks Cube

permalink

This is Part 3 of a 4-part blog post on the mathematics of the 4x4 Rubik's Cube, its relation to algorithms, and some curious properties of Rubik's Cubes.

See Part 1 of this blog post here: Part 1: Representations

See Part 2 of this blog post here: Part 2: Permutations

You are currently reading Part 3 of this blog post: Part 3: Factoring Permutations

See Part 4 of this blog post here: Part 4: Sequence Order

Table of Contents




Introduction

So far we have been discussing representations of the Rubik's Cube, with the ultimate intention of investigating some of its properties.

In this post, we define and explore the properties we are interested in studying.

Cycles

(Definition of cycle)

We use the two-line notation introduced in the last blog post, so a permutation of a 5-tuple might look like this:

$$ a = \bigl(\begin{smallmatrix} a & b & c & d & e \\ b & a & e & c & d \end{smallmatrix}\bigr) $$

In this permutation, we see that \(a\) and \(b\) swap places, and \(c\), \(d\), and \(e\) exchange places as well. These two groups form two cycles.

Think of the cycles as the particular way that pieces of the permutation are exchanged with one another.

Sequences

We are interested in studying the properties of the cube, but in particular we are interested in the properties of move sequences applied to the cube.

There are 36 possible moves on a cube, and a series of moves applied in a particular order defines a sequence. The 36 possible rotations were given in the prior blog post and cover clockwise and counterclockwise rotations of each of the six faces - either the first layer, the second layer, or both of the first two layers.

These moves are denoted with six letters (UDLRFB) for the upper, downward, left, right, front, and back face of the cube, respectively.

Moves indicated should be clockwise unless they contain an apostrophe character ', which indicates counterclockwise rotation.

A capital letter indicates a rotation of the first layer only (e.g., U indicates a clockwise rotation of the first layer of the upper face).

A lowercase letter indicates a roration of the first and second layers (e.g., r indicates a clockwise rotation of the top two layers of the right face).

A 2 before the letter indicates that the second layer should be rotated (e.g., 2F indicates a clockwise rotation of the second layer of the front face).

Each move sequence can be translated into a tuple representation (see Part 1 blog post). Once we have the tuple representation of a permutation, we can do several things, beginning with finding the cycles that compose the moves of the sequence.

Order

The quantity we are truly interested in is the order of a given cycle.

The order of a sequence of moves is the number of times that sequence must be applied to the cube to get the cube to return back to its original state. A more convenient way to think about it is, if you applied a move sequence to a solved cube, how many times would you have to apply it until you reached a solved cube again?

We begin with the move sequence, which applies a particular permutation to the cube, exchanging particular pieces in a particular order. We want to obtain a tuple representation of the permutation that results from a particular sequence of moves.

Once we have the tuple representation of a sequence's permutation, we can factor it into independent cycles using the techniques covered in this blog post.

The factoring a permutation into cycles will yield the order; the order is the least common multiple of the lengths of eacch cycle that is a factor.

Using this, we can investigate the properties of the order of different move sequences.

Intercalation Product

In Part 2 of this blog post, we discussed the tuple representation of a permutation; for example, one permutation \(\pi\) of an \(n\)-tuple might be written:

$$ \pi = \bigl(\begin{smallmatrix} 1 & 2 & 3 & \cdots & n-1 & n \\ 2 & 3 & 4 & \cdots & n & 1 \end{smallmatrix}\bigr) $$

The top row consists of the elements in the tuple in sorted order; the second row consists of elements of the tuple corresponding to that permutation.

In the discussion that follows we'll keep it general, and talk about multisets - the case in which the top row has multiple occurrences of different items.

For the following discussion, we will suppose two permutations \(\alpha\) and \(\beta\) composed of four objects \(\{a, b, c, d,\}\), each occurring multiple times:

$$ \alpha = \bigl(\begin{smallmatrix} a & a & b & c & d \\ c & a & d & a & b \end{smallmatrix}\bigr) $$
$$ \beta = \bigl(\begin{smallmatrix} a & b & d & d & d \\ b & d & d & a & d \end{smallmatrix}\bigr) $$

Definition

Now we define the intercalation product \(\alpha \top \beta\) of these permutations as the elements of each permutation organized in an interleaved way - each element of \(\alpha\) and \(\beta\) are grouped by the letter that appears on the top row, and within those groups they are ordered as they appear in \(\alpha\), then as they appear in \(\beta\).

For our example, the intercalation product is the following combination of \(\alpha\) and \(\beta\):

$$ \alpha \top \beta = \bigl(\begin{smallmatrix} a & a & b & c & d \\ c & a & d & a & b \end{smallmatrix}\bigr) \top \bigl(\begin{smallmatrix} a & b & d & d & d \\ b & d & d & a & d \end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} a & a & a & b & b & c & d & d & d & d \\ c & a & b & d & d & a & b & d & a & d \end{smallmatrix}\bigr) $$

This is basically an interleaving operation. All top-bottom pairs with \(a\) at the top are grouped together - and within the group, everyone from \(\alpha\) comes first, everyone from \(\beta\) comes second.

The first two \(a\) items in \(\alpha \top \beta\) come from \(\alpha\), the third \(a\) item comes from \(\beta\).

Side Note: Why Define an Intercalation Product?

You may be wondering what the intercalation product has to do with Rubik's Cubes or finding the order of a sequence. It turns out that the intercalation product will allow us to establish a system of permutation algebra, define certain operations and properties of permutations, and use these to factor permutations into independent groups of faces being exchanged.

Properties

We can state some properties of the intercalation algebra already:

If \(\alpha \top \pi = \beta \top \pi\) or \(\pi \top \alpha = \pi \top \beta\), this implies \(\alpha = \beta\).

An identity element exists such that \(\epsilon \top \alpha = \alpha \top \epsilon = \alpha\).

The commutative property for the intercalation product (whether \(\alpha\) and \(\beta\) can be exchanged in expressions) only holds if \(\alpha\) and \(\beta\) are independent of each other (if they permute different elements). If this condition holds, then \(\alpha \top \beta = \beta \top \alpha\).

This property does not hold in general.

(An example of permutations that would be independent on the Rubik's Cube would be the moves U and D. These each rotate a different group of faces.)

Factoring Permutations Using Knuth's Theorem A

Volume 3 of Donald Knuth's The Art of Computer Programming gives the following theorem on page 26, which gives a very useful property of intercalation products:

Theorem A. Let the elements of the multiset \(M\) be linearly ordered by the relation "<". Every permutation \(\pi\) of \(M\) has a unique representation as the intercalation

$$ \pi = ( x_{1,1} \dots x_{1,n_1} y_1 ) \top ( x_{2,1} \dots x_{2,n_2} y_2 ) \top \dots \top ( x_{t,1} \dots x_{t,n_t} y_t ) $$

where

$$ y_1 \leq y_2 \leq \dots \leq y_t $$

and

$$ y_i < x_{ij} \qquad \mbox{ for } 1 \leq j \leq n_i, 1 \leq i \leq t $$

Significance of Factors

Theorem A is central to our goal of studying move sequences (and computing their order). To understand why, consider the factors that result from Theorem A, and what they mean in the specific example of a Rubik's Cube.

In a regular n-tuple, the factors represent groups of items in the tuple that are being exchanged. A tuple that factors into the intercalation of many very small tuples means the permutation mostly consists of swapping pairs or triplets of things. A tuple that factors into the intercalation of two large tuples means, all of the things are divided into two groups, and within that group, everybody is mixed in with everybody else.

On a Rubik's Cube, the tuple consists of faces being moved, so a permutation's factors indicate how many faces are being swapped. The size of each group of faces gives some indication as to how long it takes for the cube to "sync up" with its original state if the permutation is repeatedly applied; a permutation with fewer large factors will take longer than a permutation with many small factors.

For example, suppose a move sequence permutes three corner pieces on a cube each time it is applied. Then if we write the two-line tuple corresponding to that permutation, and we factor it into the intercalation product of several tuples, several factors of the permutation will have a length of three, and will contain the set of three faces being exchanged.

On the other hand, if a move sequence permutes six corner pieces on a cube each time it is applied, some of the factors will be groups of six faces being exchanged when the sequence is applied.

Thus, the (sizes of the) factors of a permutation determine the order of the permutation.

How to Factor Permutations

To factor a permutation, we perform the opposite of the intercalation product. Now supppose we wish to factor the permutation:

$$ \pi = \bigl(\begin{smallmatrix} a & a & b & b & b & b & b & c & c & c & d & d & d & d & d \\ d & b & c & b & c & a & c & d & a & d & d & b & b & b & d \end{smallmatrix}\bigr) $$

into the intercalation of multiple independent, disjoint cycles,

$$ \pi = \alpha \top \beta \top \dots \top \gamma $$

We can extract each factor one at a time using the following algorithm.

Start by assuming the first factor \(\alpha\) contains the first symbol \(a\) in its top row.

(It turns out this assumption can't be false - if there is an \(a\) in the top row of \(\pi\) then there is an \(a\) in the top row of at least one factor. We're simply going to pull out those factors with this assumption.)

Given this assumption, we know \(\alpha\) must map \(a\) to the same letter as the final permutation maps \(a\) to, in the very first column of \(\pi\). The first column of \(\pi\) is \(( a d )\) (a on top, d on bottom). That means that if our assumption holds, if \(\alpha\) contains \(a\), then it must permute all \(a\)'s into \(d\)'s and thus \(\alpha\) should contain the same column \((a d )\).

Now suppose that \(\alpha\) contains \(d\), which it must if our prior step is true. (\(\alpha\) cannot turn \(a\) into \(d\) if it does not have a \(d\)!). We find the leftmost \(d\) on the top line, and see that it maps to the symbol \(d\), due to the column \(( d d )\) (d on top, d on bottom). Thus, \(\alpha\) should also contain the column \(( d d )\).

We keep going. Suppose that \(\alpha\) contains another \(d\), as a consequence of the prior step. Since we already used the first d column in \(\pi\), we use the next column, \(( d b )\) Thus, \(\alpha\) should also contain the column \(( d b )\), and we use the outcome \(b\) as the starting point for the next step.

The process stops as soon as the starting point for the next step is the letter we began with, \(a\). That's because, at that point, we've formed a "closed loop" of pieces that permute with one another. That closed loop forms the first intercalation factor of the permutation \(\pi\).

If we keep repeating the process described, we eventually wind up with \(\alpha\):

$$ \alpha = \bigl(\begin{smallmatrix} a & d & d & b & c & d & b & b & c \\ d & d & b & c & d & b & b & c & a \end{smallmatrix}\bigr) $$

Side Note: Why Does This Work?

Let's pause for a moment and see what's happening. What we're doing is following a thread between the top and bottom rows of the permutation; this thread tells us how elements are being moved around to create permutations.

(A simpler but easier way to see this is by comparing two permutations of \((1 2 3 4 5 6)\): consider the permutation \((2 1 3 4 6 5)\), versus the permutation \((2 4 5 6 1 3)\). The first permutation swaps positions 0 and 1, and positions 4 and 5, independently; the second permutation mixes all positions together.)

We are assembling \(\alpha\) piece by piece, by pulling out pairs from the top and bottom row of \(\pi\) and putting them into \(\alpha\). At some point we will come back to the starting point, the symbol \(a\), and we will be finished finding the first factor \(\alpha\), which is a disjoint cycle.

By starting from the top row and following where it leads in the bottom row, and continuing until we return to the original starting element in the top row, we can carve up the permutation into groups of pieces exchanged with one another and not with any other pieces, or groups of pieces that don't move.

How to Factor Permutations (Cont'd)

Recall that our goal was to factor the permutation \(\pi\) into the intercalation of multiple independent and disjoint cycles, \(\pi = \alpha \top \beta \top \dots \top \gamma\). We gave a procedure to extract factors and used it to extract the first factor, \(\alpha\).

However, this is not the end of the factoring process: there are still several elements of \(\pi\) that have not been used to form \(\alpha\), and those remaining elements themselves form a permutation that can be factored.

We begin with the original permutation \(\pi\):

$$ \pi = \bigl( \begin{smallmatrix} a & a & b & b & b & b & b & c & c & c & d & d & d & d & d \\ d & b & c & b & c & a & c & d & a & d & d & b & b & b & d \end{smallmatrix}\bigr) $$

When we pull out the first factor \(\alpha\), we get:

$$ \pi = \bigl( \begin{smallmatrix} a & d & d & b & c & d & b & b & c \\ d & d & b & c & d & b & b & c & a \end{smallmatrix} \bigr) \top \bigl( \begin{smallmatrix} a & b & b & c & d & d \\ b & a & c & d & b & d \end{smallmatrix} \bigr) $$

When we pull out the second factor \(\beta\), we get:

$$ \pi = \bigl( \begin{smallmatrix} a & d & d & b & c & d & b & b & c \\ d & d & b & c & d & b & b & c & a \end{smallmatrix} \bigr) \top \bigl( \begin{smallmatrix} a & b \\ b & a \end{smallmatrix} \bigr) \top \bigl( \begin{smallmatrix} b & c & d & d \\ c & d & b & d \end{smallmatrix} \bigr) $$

The third factor can be pulled out as well, which leaves the last factor, a single column \(( d d )\) by itself, indicating an element that is not moved by the permutation.

$$ \pi = \bigl( \begin{smallmatrix} a & d & d & b & c & d & b & b & c \\ d & d & b & c & d & b & b & c & a \end{smallmatrix} \bigr) \top \bigl( \begin{smallmatrix} a & b \\ b & a \end{smallmatrix} \bigr) \top \bigl( \begin{smallmatrix} b & c & d \\ c & d & b \end{smallmatrix} \bigr) \top \bigl( \begin{smallmatrix} d \\ d \end{smallmatrix} \bigr) $$

Thus the permutation \(\pi\) can be expressed as the intercalation of four independent cycles.

This procedure illustrates Knuth's Theorem A.

(Note: had we initially assumed \(\alpha\) 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.)

To relate this back to the Rubik's Cube, we can start with a sequence of interest, like U R D D B, and write the tuple representing the outcome of this sequence when it is applied to the cube. In this way we represent a move sequence as a tuple or as a permutation.

Next, we factor this permutation the way we factored \(\pi\), into the intercalation product of independent cycles. These are groups of pieces being swapped each time the cycle is applied.

Now if one factor is of length 4 (group of 4 faces being permuted), one factor is of length 3, and one factor is of length 20, then the number of times the sequence must be applied before the cube will come back to its original, solved state is \(LCM(3,4,20) = 60\).

Algorithm A

Algorithm A is an algorithm written to perform the factoring process described above.

We started with the two-row representation above, so our function will start with the top and bottom rows of the two-row representation.

The procedure started with the first entry of the top row, and got the corresponding entry of the bottom row. It then moved to the index of that item on the top row, and got the coresponding entry of the bottom row, and so on, assembling the components of the permutation by stepping through each.

In code, this will require us to switch between items in a list, and the indices of occurrencs of items in the list. Fortunately, this is an easy and common operation.

Following is the pseudocode, then the Python code, to implement Algorithm A on the two-row representation of a tuple.

Pseudocode

Our function takes two arguments: the top and bottom rows of the two-row representation of this permutation.

define function factor_permutations( top row, bottom row )

    create bit vector to mark columns as factored or not

    initialize list of factors

    initialize pointer to active location

    initialize starting index

    while there are still zeros in the bit vector:

        initialize this factor

        run until break reached:

            set bit vector at active location to 1

            get active location entries on top row (leader) and bottom row (follower)

            get next active location (index of follower in top row)

            break if next active location out of bounds

            break if next active location is starting element

            append follower to this factor

        add starting element to end of factor

        add factor to list of factors

        set next start index to index of first 0 in bit vector

    return factors

Python Code

(Code for Algorithm A)

def factor_permutation(perm_top,perm_bot):
    """
    Factor a permutation into its lowest terms
    """
    MAX = 96
    # Need a way to also mark them as used... bit vector
    used_vector = [0,]*len(perm_top)

    i = 0
    start = perm_top[0]
    used_vector[0] = 1

    factors = []

    # If we still have values to pick out:
    while(0 in used_vector):

        factor = []

        while(True):
            used_vector[i] = 1
            leader = perm_top[i]
            follower = perm_bot[i]

            i = perm_top.index(follower)
            while(used_vector[i]==1):
                i += 1
                if(i>=MAX):
                    break

            if(i>=MAX):
                break
            elif(follower==start):
                break
            else:
                factor.append(follower)

        # add start to end
        factor.append(start)

        factors.append(factor)
        try:
            i = used_vector.index(0)
            start = perm_top[i]
        except ValueError:
            break

    factorsize = set()
    check = 0
    for factor in factors:
        factorsize.add(len(factor))
        check += len(factor)
    return factors

Preview of Part 4

We concluded with an algorithm that will be central to our task of computing the order of a Rubik's Cube move sequence.

In the next post, we'll apply our method of representing Rubik's Cubes using the two-line tuple notation, and use the factoring algorithm above, which will allow us to factor Rubik's Cube permutations into their corresponding intercalation products.

From there, we can count the size of each intercalation product, and the least common multiple of the sizes gives the order of the permutation.

References

  1. "Rubik's Cube". Charlesreid1.com wiki, Charles Reid. Edited 20 January 2017. Accessed 20 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube>

  2. "Rubik's Revenge". Charlesreid1.com wiki, Charles Reid. Edited 20 January 2017. Accessed 20 January 2017. <https://charlesreid1.com/wiki/Rubiks_Revenge>

  3. "Rubik's Cube/Tuple". Charlesreid1.com wiki, Charles Reid. Edited 20 January 2017. Accessed 20 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Tuple>

  4. "Rubik's Cube/Permutations". Charlesreid1.com wiki, Charles Reid. Edited 20 January 2017. Accessed 20 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Permutations>

  5. "Github - dwalton76/rubiks-cube-NxNxN-solver". dwalton76, Github Repository, Github Inc. Accessed 11 January 2017. <https://github.com/dwalton76/rubiks-cube-NxNxN-solver>

  6. "Rubik's Cube NxNxN Solver". Git repository, git.charlesreid1.com. Charles Reid. Updated 20 January 2017. <https://git.charlesreid1.com/charlesreid1/rubiks-cube-nnn-solver>

  7. "Rubiks Cube Cycles". Git repository, git.charlesreid1.com. Charles Reid. Updated 20 January 2017. <https://git.charlesreid1.com/charlesreid1/rubiks-cube-cycles>

Tags:    rubiks cube    combinatorics    permutations    python    puzzles    art of computer programming    knuth   

May 2018

Current Projects