According to Problem 24 in
Project Euler, you are asked to find the millionth permutation using the
following sequence of 10 digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Well, if
you do the math, there are around ** 10! = 3,628,800 unique
permutations** and that means, you have to come up with an efficient
algorithm.

I tried writing a recursive function but it turned out to be a bit tricky, so I thought of writing a brute-force solution which seemed far more simpler to understand and it's quite efficient.

## Algorithm Description

The following algorithm is quite simple and easy to understand:

` ````
1. Find i such that a[i-1] is greater than or equal to a[i].
2. Find j such that a[j-1] is less than or equal to a[i-1].
3. Swap a[i] with a[j].
4. Reverse the suffix from a[i+1] to the last element.
```

Suppose, if the first step fails, it means the current permutation is the last one because such an index that does not exist. However, it's simple to implement the following algorithm correctly and efficiently, so let's take a look at the implementation.

## Python Implementation

The following method only generates the next permutation of any given sequence, so if you're interested in generating all the permutations, especially, for very large lists, this function can be useful.

**Implementation of the method(s):**

` ````
# Swap numbers in a list
def swap(list, i, j):
list[i], list[j] = list[j], list[i]
# Get the next permutation
def nextPermutation(list):
i = len(list) - 1
# As long as the f(x-1) >= f(x), decrement the first index
while list[i-1] >= list[i]:
i = i-1
j = len(list)
# As long as the f(y-1) <= f(x-1), decrement the second index
while list[j-1] <= list[i-1]:
j = j-1
# make a swap
swap(list, i-1, j-1)
i = i+1
j = len(list)
# keep swapping until you get the next permutation
while i < j:
swap(list, i-1, j-1)
i = i+1
j = j-1
return list
```

**Final code:**

` ````
#!usr/bin/python
import math, time, pe_lib
start = time.time()
list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 1
limit = 1000000
while count < limit:
pe_lib.nextPermutation(list)
count = count + 1
print "".join(str(x) for x in list)
print "Finished: %f seconds" % (time.time() - start)
```

This code in executed in approximately **2.37 seconds** with an
algorithmic complexity of **O(n)** i.e. linear time complexity and the
replacements of the numbers were done
in-place since no
extra space was used.

Hope you liked reading this article!