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 EnglandWe 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.
I’m not sure how md2perpe did it, but when I was developing this problem I initially solved it by hand.
Anyway, i have moved into level 1 and got myself a badge here