Dec

27

Project Euler: nth lexicographic permutation

Filed Under hisabati, project euler by | Leave a Comment

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!

Dec

16

Project Euler: Determining the number of paths in a grid

Filed Under hisabati, project euler by | Comments Off on Project Euler: Determining the number of paths in a grid

For problem 15 from Project Euler, we are asked to find the number of paths leading from the top left corner of a grid to the bottom right corner that do not involve backtracking.

Starting in the top left corner of a 2 by 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 by 20 grid?

Given the way the problem is set up, for any one node there are at most two nodes that can lead directly to the node. If we assign coordinates to the grid with (0,0) being the top-left corner, the only nodes that have direct outgoing paths to (1,1) are (0,1) and (1,0). Trivially, each of the nodes in row 0 (the top row) has only one node that can lead into it (the node immediately to its left). Similarly, nodes in column 0 (the left-most column) each have one node leading into them (the node immediately above them). We can use this information to calculate the number of paths ending at any one node in the grid.

To do this, consider nodes A, B and C that form the lower right triangle of an arbitrary square in the grid. We label the nodes such that A is the lower left corner of the square, B is the lower right corner while C is the upper right corner of the square. As shown before, the only way to get a path ending at B is to take a path ending at either A or C and add one step to it. We also know that a path ending at A cannot pass through C (since we don’t allow backtracking) and similarly a path ending at C cannot pass through A. Therefore, the number of paths ending at B = number of paths ending at A + number of paths ending at C.

This leads to the following rather short algorithm:

  1: def num_paths_to_grid_bottom(numRowCells, numColumnCells):
  2:     currRow = [1 for x in range(numColumnCells + 1)]
  3:     # the number of nodes to consider = numRowCells + 1
  4:     for numRow in range(1, numRowCells + 1):
  5:         for numColumn in range(1, numColumnCells + 1):
  6:             currRow[numColumn] += currRow[numColumn - 1]
  7:     return currRow[numColumnCells]