Project Euler Problem 024

# Statement

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?

# Solution

For this problem we need to find the 999999th element of a 10 element permutation if
using 0-index based.
With 9 elements we have 362880 combinations, so for each 362880 combinations we change
the first digit. So: 999999 / 362880 = 2 -> so we pick the digit in position 2(0-based index) from
the list of digits place it as first digit of the result and remove it from the list.
Then we have to find the 999999 mod 362880 = 274239th combination from 8 element permutations

We follow the same technique applied for the first case, this can be done easily with pencil and paper
but like we are programming let's do it in Python:

```from CommonFunctions import factorial

def combinations(n, r):
return factorial(n) // (factorial(n - r))

if __name__ == '__main__':
number = 999999
lst = list(range(10))
result = []
for i in range(9, -1, -1):
comb = combinations(i, i)
index = number // comb
number = number % comb
result.append(str(lst.pop(index)))
print("The result is:", ''.join(result))
```