I Think

Problem 24

Problem 24 in euler’s deals with getting the millionth lexicographical permutation of the digits 0-9. Generating permutations is not a big deal, quickly plunged into the problem and brute forced it into submission.


def problem24():
    def perms_gen(seq):
        if len(seq):
            for i in range(len(seq)):
                curr = seq[i]
                remaining = seq[:i] + seq [i+1:]
                for gen in perms_gen(remaining):
                    yield [curr] + gen
        else:
            yield []

    i = 1
    perms = perms_gen(range(10));
    while i < 1000000:
        perms.next()
        i+=1
    print ''.join([str(i) for i in a.next()])

problem24()

The drawback was that the whole thing ran for over 10 seconds. Anyway after unlocking the problem, I checked out some of the solutions and had a why-dint-i-think-of-that moment reading this.

euler   (PHP)  euler is from England
I’m not sure how md2perpe did it, but when I was developing this problem I initially solved it by hand.

We know that there are n! permutations for n distinct digits and, as we’re working in lexicographical order, after 9! permutations the ten digit string will have become: 0987654321. The 9!+1 permutation will be 1023456789, the 2*9!+1=725761 permutation will be 2013456789. However, the 3*9!+1 permutation (3012456789) will be greater than one million. So we now consider the permutations of the last nine digits, 013456789: 6*8!+1 will take it to 701345689. We have now computed 967681 permutations and arrived at the number 2701345689. Then we look at the last eight digits, and work out that a further 6*7!+1 takes it to the string 2780134569 and a total of 997921 permutations…

Once I discovered this method, and rather than continue by hand, I wrote a programme to complete this (tedious) task for any given number of permutations.

Anyway, i have moved into level 1 and got myself a badge here

Advertisements
Standard