Problem 24

I’ll start with Project Euler. I like to learn new things by practice and some problems seem simple enough to learn groovy. Let me just start with Problem 24.

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

It should be simple to do it in groovy. I didn’t find method permutate for lists or any other collections. There is none in google collections. Since it couldn’t be so simple, I tried something different…

def l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
def input = []
l.each {
    input << l
}

List permutations = input.combinations().findAll { List list ->
    list.containsAll(l)
}
permutations = permutations.collect {it.reverse()} // shorter version: permutations = permutations*.reverse() - calls reverse on each element
println permutations

Building permutations from combinations looks awkward, but surprisingly it works:) The catch is that it works only for small numbers.

Since built in methods don’t work, it’s time to use some superpowers and code the algorithm for finding permutations.
I didn’t want to iterate over every permutation, so I made a quick search. And I found factoradics. It’s a factorial number system – one of number systems with mixed radix. It can be used to describe a permutation and works perfectly.
So there are two steps to find the permutation:

1. Find factoradic representation of 999999 – it’s millionth permutation as we start indexing from 0
2. Get permutation from factoradic.

Let’s find factoradic representation.

To get factoradic digits a normal division algorithm is enough.
First you divide the input number by 1 – the remainder is always 0 and quotient is our 999999
Divide the quotient by 2 – the remainder is 1 and quotient is 499999
Divide the quotient by 3 – the remainder is 1 and quotient is 166666
and so on…

We’ll receive the factoradic representation: [0, 1, 1, 2, 1, 5, 2, 6, 6, 2].
The n-th number is the coefficient of n!. This can be turned into decimal number by multiplying each number by n-th factorial:
0*0! + 1*1! + 1*2! + 2*3! + 1*4! + 5*5! + 2*6! + 6*7! + 6*8! + 2*9!

int numberOfDigits = 10
int decimalNumber = 999999
def factoradic = []
(1..numberOfDigits).inject(decimalNumber) {previousResult, currentNumber ->
    int moduloResult = previousResult % currentNumber
    int integerResult = (int) previousResult / currentNumber

    factoradic << moduloResult
    integerResult
}
println factoradic

The output is: [0, 1, 1, 2, 1, 5, 2, 6, 6, 2]

The groovy’s inject method is very useful here. It’s used to find successive modulo results.
A simple example of using the inject method to find factorials:

def factorials = (1..10).inject([1]) {list, currentElement ->
    list << currentElement * list[-1]
    list
}
println "factorials = $factorials"

The output is:
factorials = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

We start with list that contains only 1 and pass it through to next invocation. Each time next factorial is added to the list.

Finding permutation from factoradic

Each digit in factoradic representation is treated as index of digit in ascending list. Each time picked digit is removed from list. That’s why the last digit of factoradic is always 0. There’s only one element in the list left and it’s index is 0.
Let’s see how it works for couple first numbers of our 999999 representation: 2662512110

Digits: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Removing 2nd number – 2 and left with [0, 1, 3, 4, 5, 6, 7, 8, 9]
Removing 6th number – 7 and left with [0, 1, 3, 4, 5, 6, 8, 9]
Removing 6th number – 8 and left with [0, 1, 3, 4, 5, 6, 9]
and so on…

When we finish, the list should be empty and the numbers are our millionth permutation of 10 digits.

Of course this didn’t go so smooth… Implementation was straightforward, but the most time took me discovering that 1000000 is the 1000001th permutation: “There has to be an issue on Project Euler’s site, I can’t be wrong”.