449,103 Members | 1,130 Online
Need help? Post your question and get tips & solutions from a community of 449,103 IT Pros & Developers. It's quick & easy.

# Permutation Generator

 P: n/a 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 Aug 12 '05 #1
10 Replies

 P: n/a In article , 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 You're right that you're not the first person to do this: Many others have also posted incorrect permutation generators. Have you tried your code on some simple test cases? list(permute([1, 2, 3])) ==> [[1, 2, 3], [2, 3, 1], [1, 3, 2], [3, 2, 1]] Notably absent from this list are [2, 1, 3] and [2, 3, 1]. The problem gets worse with longer lists. The basic problem is that x needs to be able to occur in ALL positions, not just the beginning and the end. Cheers, -M -- Michael J. Fromberger | Lecturer, Dept. of Computer Science http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA Aug 12 '05 #2

 P: n/a Talin writes: 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 Hmm: for p in permute([1,2,3]): print p [1, 2, 3] [2, 3, 1] [1, 3, 2] [3, 2, 1] Oops. Aug 12 '05 #3

 P: n/a "Talin" wrote in message news:ma***************************************@pyt hon.org... I wanted to share this: a generator which returns all permutations of a list: Try this instead: def permuteg(lst): return ([lst[i]]+x for i in range(len(lst)) for x in permute(lst[:i]+lst[i+1:])) \ or [[]] Alan Isaac Aug 13 '05 #4

 P: n/a On Fri, Aug 12, 2005 at 03:48:38PM -0400, Michael J. Fromberger wrote: In article , 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: You're right that you're not the first person to do this: Many others have also posted incorrect permutation generators. Amen, combinatorics are so popular they should be in the FAQ. groups.google.com can show you many pure python recipies and benchmarks, but I'll give my ususal response: http://probstat.sourceforge.net/ I'm not just the author, I'm a client-ly, -jackdied Aug 14 '05 #6

 P: n/a It's hard to make "complete" permutation generators, Knuth has a whole fascicle on it - "The Art of Computer Programming - Volume 4 Fascicle 2 - Generating All Tuples and Permutations" - 2005 -- Regards, Casey Aug 14 '05 #7

 P: n/a "Casey Hawthorne" wrote in message news:s1********************************@4ax.com... It's hard to make "complete" permutation generators, Knuth has a whole fascicle on it - "The Art of Computer Programming - Volume 4 Fascicle 2 - Generating All Tuples and Permutations" - 2005 Can you elaborate a bit on what you mean? Given a list of unique elements, it is easy enough to produce a complete permutation generator in Python, in the sense that it yields every possible permuation. (See my previous post.) So you must mean something else? Cheers, Alan Isaac PS If the elements are not unique, that is easy enough to deal with too, as long as you say what you want the outcome to be. Aug 14 '05 #8

 P: n/a Just satisfied my curiosity wrt this problem, so I might as well share :-) def permute(list): .... if len(list) <= 1: .... yield list .... else: .... for i in xrange(0,len(list)): .... for tail in permute( list[:i] + list[i+1:] ): .... yield [ list[i] ] + tail .... for o in permute([1,2,3]): .... print o .... [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] regards Matt On Fri, 12 Aug 2005 20:48:38 +0100, Michael J. Fromberger wrote: In article , 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 You're right that you're not the first person to do this: Many others have also posted incorrect permutation generators. Have you tried your code on some simple test cases? list(permute([1, 2, 3])) ==> [[1, 2, 3], [2, 3, 1], [1, 3, 2], [3, 2, 1]] Notably absent from this list are [2, 1, 3] and [2, 3, 1]. The problem gets worse with longer lists. The basic problem is that x needs to be able to occur in ALL positions, not just the beginning and the end. Cheers, -M -- | Matt Hammond | R&D Engineer, BBC Research and Development, Tadworth, Surrey, UK. Aug 15 '05 #9

 P: n/a On Mon, 15 Aug 2005, Matt Hammond wrote: Just satisfied my curiosity wrt this problem, so I might as well share :-) def permute(list): How about: def permutation(l, i): "Makes the ith permutation of the sequence l." # leave out the reverses if you don't care about the order of the permutations l_ = []; l_[:] = l; l_.reverse() m = [] for j in xrange(len(l_)): m.append(l_.pop((i % len(l_)))) i = i / (len(l_) + 1) m.reverse() return m def factorial(n): if (n == 1): return 1 else: return n * factorial((n - 1)) def permute(l): for i in xrange(factorial(len(l))): yield permutation(l, i) for o in permute([1,2,3]): print o .... [1, 2, 3] [1, 3, 2] [2, 3, 1] [2, 1, 3] [3, 1, 2] [3, 2, 1] The thing i like about doing it this way is that you can use permutation(l, i) to make arbitrary permutations on their own, should you ever need to do that. Also, it gives you an easy way to make only the even permutations of a list - just feed even numbers into permutation(l, i) (i think!). This could be useful if you wanted to build an alternating group for some obscure discrete mathematics purpose. tom -- The future is still out there, somewhere. Aug 15 '05 #10

 P: n/a 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 Aug 15 '05 #11

### This discussion thread is closed

Replies have been disabled for this discussion.