nxtperm.py

#!/usr/bin/env python
#
# Author:  Yotam Medini  [email protected] -- Created: 2006/May/11
#
# Next Permutation
#

import sys


def next_permutation(a):
    n = len(a)
    # Find last increasing pair
    i = n - 2
    while i >= 0 and a[i] >= a[i+1]:
        i -= 1
    if i < 0:
        a = None  # a is decreasing, no more permutations
    else:
        # Find last greater than a[i].
        # There must be one! since a[i] < a[i+1].
        j = n - 1
        while a[i] >= a[j]:
            j -= 1
        # and swap
        t = a[i];  a[i] = a[j];  a[j] = t

        # Mirror the tail. Swap pairs from going from the sides to the center
        low = i + 1
        high = n - 1
        while low < high:
            t = a[low];  a[low] = a[high];  a[high] = t
            low += 1
            high -= 1
    return a


# Program begins
n = 3;  # Just a guess
if len(sys.argv) > 1:
    n = int(sys.argv[1])
a = range(n) # First (increasing) permutation
permi = 0
while a != None:
    sys.stdout.write("Permutation[%3d] = %s\n" % (permi, a))
    a = next_permutation(a)
    permi += 1
sys.stdout.write("Total %s Permutations\n" % permi)
sys.exit(0)