Talin wrote:
> I'm sure I am not the first person to do this, but I wanted to share
> this: a generator which returns all permutations of a list:
>
> def permute( lst ):
> if len( lst ) == 1:
> yield lst
> else:
> head = lst[:1]
> for x in permute( lst[1:] ):
> yield head + x
> yield x + head
> return
>
> -- Talin
As it happens, I've just started learning Python and my 'Hello World'
was a class which generates all permutations of the set {1,2,...n}.
It's a translation of some Pascal code from the book "Programming for
Mathematicians" by Raymond Seroul (2000 Springer-Verlag), and produces
a (non-lexicographic) total ordering of the set using Johnson's
Algorithm.
To explain the algorithm briefly. Each element is 'adorned' with a flag
( either 1 or -1 ) which determines the direction that an element is
'looking' - so, given the sequence
[ [-1,3], [1,2], [1,1], [-1,4] ]
1 sees 4
2 sees 1
3 sees nothing
4 sees 1
(with the convention that -1 means 'looking left')
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
- 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
In coding the algorithm, sentinels with value 1 bigger than n are added
at either end of the sequence, this helps when checking which elements
are mobile. Also, 1 and -1 aren't arbitrary flags, these values are
used because you can find which element another element 'sees' by using
'index + flag'.
Here's the code:
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
class NPermutation( Permutation ):
def __init__( self, n ):
Permutation.__init__( self, range( 1, n+1 ) )
self.reset()
def reset( self ):
list = [ [-1,i] for i in range(self.length+2) ]
list[0][1] = self.length+1
#eg. n=3 -> list = [[-1,4], [-1,1], [-1,2], [-1,3], [-1,4]]
self.__current = list
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
Gerard Flanagan
15/8/05
--
http://mail.python.org/mailman/listinfo/python-list
