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!

References