Utilities
Algorithms

Johnson's Algorithm

This is a translation of some Pascal code from the book Programming for Mathematicians by Raymond Seroul (2000 Springer-Verlag). It is an implementation of Johnson's Algorithm(1963) which produces a non-lexicographic, total ordering of the set Sn of permutations of the set { 1, 2,..., n }. The algorithm is described below.

The base class, Permutation, will permute any list or string and could, for example, be used to generate a random string as follows: 

 >>>import string
 >>>choice = string.letters
 >>>print choice
 abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ              
 >>>perm = Permutation( choice )
 >>>random_string = ''.join(perm.random())
 >>>print random_string
 oGqWNbsYxLjmzAQhvTPFKJwZSOckiaCMRytndEfrXUHgIlpuVBDe
 >>>print random_string[:10]
 oGqWNbsYxL


def factorial( n ):
    if n <= 1:
        return 1
    else:
        return n * factorial( n-1 )

class Permutation:

    def __init__( self, items ):
        seq = list( items[:] )
        n = len( seq )
        self.sequence = seq
        self.length = n
        self.count = factorial( n )
 
    def __getitem__( self, key ):
        result = []
        sequence = self.sequence[:]
        N = self.count
        index = key
        for i in range( self.length, 0, -1):
            N = N / i
            choice, index = index // N, index % N
            result += [ sequence.pop(choice) ]
        return result
 
     def random(self):
        import random
        i = random.randint(0,self.count-1)
        return self[i]
        
        
class NPermutation( Permutation ):
 
    def __init__( self, n ):
        Permutation.__init__( self, range( 1, n+1 ) )
        self.reset()
 
    def reset( self ):
        alist = [ [-1,i] for i in range(self.length+2) ]
        alist[0][1] = self.length+1
        #eg. n=3 -> alist = [[-1,4], [-1,1], [-1,2], [-1,3], [-1,4]]
        self.__current = alist
        self.__index = 0
        
    def __iter__( self ):
        return self
 
    def next( self ):
        if self.__index == self.count:
            self.reset()
            raise StopIteration
        elif self.__index > 0:
            j = self.__get_index_of_highest_mobile()
            #remember the mobile itself before you move it
            mobile = self.__current[j][1]
            #swap the mobile with the element it 'sees'
            self.__move_mobile_at_index( j )
            #switch the direction of elements greater than mobile
            if mobile < self.length:
                self.__reorient_list_elements( mobile )
                
        self.__index += 1
        return [ a[1] for a in self.__current[ 1:self.length+1 ] ]
 
    def __get_index_of_highest_mobile( self ):
        high_value = 0
        high_index = 0
        for i in range( 1, self.length+1 ):
            direction = self.__current[i][0]
            value = self.__current[i][1]
            if value > high_value and \
            value > self.__current[i+direction][1]:
                high_value = value
                high_index = i
        return high_index
 
    def __move_mobile_at_index( self, index ):
        direction = self.__current[index][0]
        value = self.__current[index][1]
        self.__current[index] = self.__current[index+direction]
        self.__current[index+direction] = [direction,value]
 
    def __reorient_list_elements( self, mobile ):
        for i in range( 1, self.length+1 ):
            if self.__current[i][1] > mobile:
                self.__current[i][0] = -self.__current[i][0]
 
 
 
x = NPermutation( 6 )
 
print 'loop with __getitem__'
print '---------------'
for i in range( x.count ):
    print x[i]
 
print 'loop with __iter__'
print '---------------'
for perm in x:
    print perm
The Algorithm

Take the case n = 4 : so we want to generate all permutations of the set { 1,2,3,4 }. Each element of the set is given a flag ( 'left' or 'right', say ) which determines the direction that an element is 'looking'. We start off with the sequence:

[ ['left',1], ['left',2], ['left',3], ['left',4] ]

and, in the course of the algorithm, we might have the situation:

[ ['left',3], ['right',2], ['right',1], ['left',4] ]

in which case, we say

1 sees 4
2 sees 1
3 sees nothing
4 sees 1

The direction flag is clearly a boolean quantity, but it simplifies calculations if we represent the flag with 1 or -1, rather than 0 or 1 ( because then, we can find which element another element 'sees' by using 'index + flag'.

An element is said to be 'mobile' if it is looking at a smaller number. eg. in the sequence above, both 2 and 4 are mobile.

Then the algorithm is:

- find the highest mobile; if none exists, stop
- swap this mobile with the element it sees, but don't swap their direction flags
- reverse the direction flags of any element larger than the mobile

(The code above doesn't follow this exactly, it uses rather the foreknowledge that there are n! permutations in total, and loops accordingly.)

In coding the algorithm, sentinels with value 1 bigger than n are added at either end of the sequence, this removes the need to treat the left and rightmost elements as special cases.

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[4, 1, 3, 2]
[1, 4, 3, 2]
[1, 3, 4, 2]
[1, 3, 2, 4]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[4, 3, 2, 1]
[3, 4, 2, 1]
[3, 2, 4, 1]
[3, 2, 1, 4]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[2, 4, 1, 3]
[2, 1, 4, 3]
[2, 1, 3, 4]