Dec
27
Project Euler: nth lexicographic permutation
Filed Under hisabati, project euler by Mucheru
Problem 24 from Project Euler asks us to find the nth lexicographic permutation of a sequence of digits:
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
My first instinct was to write a routine that would enumerate permutations of a sequence of digits in lexicographic order. This would involve two functions: the first would take a permutation and return the next lexicographic permutation of the digits. The next function would call the first 999999 times, starting with the first sequence (0123456789) and passing intermediate values as it went along. The main function is below.
1: def next_lexicographic_permutation(currPermutation): 2: digits = [int(x) for x in str(currPermutation)] 3: maxIndex = len(digits)-1 4: prevValue = digits[maxIndex] 5: currValue = digits[maxIndex] 6: for i in range(maxIndex, -1,-1): 7: currValue = digits[i] 8: if (i == 0) and (currValue == max(digits)): 9: return currPermutation 10: if(currValue < prevValue): 11: prefix = digits[:i] 12: suffix = digits[i:] 13: nextStart = min([x for x in suffix if x > currValue]) 14: suffix.remove(nextStart) 15: suffix.sort() 16: nextPermutation = "".join([str(x) for x in prefix]) +str(nextStart)+ "".join([str(x) for x in suffix]) 17: return nextPermutation 18: else: 19: prevValue = currValue 20: return currPermutation 21:
While this approach worked, the operation took 30 seconds. After looking at the problem for a while longer and consulting my muse, I realized that we could directly determine the nth permutation. It is an established fact that given a set of m elements, the number of permutations possible is given by m!( read as “m factorial”, defined here). So for our set of 10 digits, there are 10! possible permutations. Of these permutations, 1/10 of them have 0 as the first digit, 1/10 have 1 as the first etc. This comes to 9! = 362,880 permutations starting with any one digit. Since sequences are presented in lexicographic order, we know that the millionth permutation has to start with 2 ( the sequences starting with 0 end at 9! and those starting with1 end at 2*9!).
The millionth permutation of 10 digits will be the 274240th permutation from the set of permutations starting with 2 (i.e. 1000,000 – 2*9!, accounting for the permutations that started with 0 and 1). The problem of determining the 274240th permutation from the set of permutations starting with 2 is equivalent to the problem we’ve just solved for 10 digits, except that this time we are determining the 274240th permutation of the digits 013456789. To solve it,we apply the same algorithm as we did previously giving a rather neat recursive solution to the general problem.
1: def nth_lexicographic_permutation(initialPermutation, n): 2: currPermutation=str(initialPermutation) 3: if len(currPermutation) == 1: return initialPermutation 4: residue = n 5: # number of permutations starting with any one digit 6: numSuffixPermutations = factorial(len(currPermutation) - 1) 7: outputDigitIndex = 0 8: if(numSuffixPermutations < residue): 9: outputDigitIndex = residue / numSuffixPermutations 10: if(residue % numSuffixPermutations == 0): 11: outputDigitIndex -= 1 12: residue -= (outputDigitIndex * numSuffixPermutations) 13: indexDigit = currPermutation[outputDigitIndex] 14: currPermutation = currPermutation.replace(indexDigit,'') 15: return indexDigit + nth_lexicographic_permutation(currPermutation, residue) 16:
This second solution runs in less than a second!