Project Euler Problem 24 Solution

Lexicographic permutations

Problem 24

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?

Answer: 2783915460

Learning:

Writing an algorithm for Permutations

#1 Recursive Approach:

def get_all_permutations(string):
  if len(string) == 1:
    return [string]

  result = []
  for i, c in enumerate(string):
    for k in get_all_permutations(string[:i] + string[i+1:]):
      result = result + [c + k]

  return result


for i, p in enumerate(get_all_permutations('0123456789')):
  if i+1 == 1000000:
    print p
    break


NOTE: When ran on large numbers,  it takes huge time to complete


 #2 Python API:
import itertools
perms = itertools.permutations('0123456789')

for i, p in enumerate(perms):
  if i+1 == 1000000:
    print ''.join(p)
    break

NOTE: It executes extremely fast, MUST SEE HOW IS IT IMPLEMENTED