Permutation Generator

Discussion in 'Python' started by Talin, Aug 12, 2005.

  1. Talin

    Talin Guest

    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
    Talin, Aug 12, 2005
    #1
    1. Advertising

  2. 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
    Michael J. Fromberger, Aug 12, 2005
    #2
    1. Advertising

  3. Talin

    Paul Rubin Guest

    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.
    Paul Rubin, Aug 12, 2005
    #3
  4. Talin

    David Isaac Guest

    "Talin" <> wrote in message
    news:...
    > I wanted to share
    > this: a generator which returns all permutations of a list:



    Try this instead:
    def permuteg(lst): return ([lst]+x
    for i in range(len(lst))
    for x in permute(lst[:i]+lst[i+1:])) \
    or [[]]

    Alan Isaac
    David Isaac, Aug 13, 2005
    #4
  5. On Fri, 12 Aug 2005 12:39:08 -0700, 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


    If we are sharing permutation algorithms today, here's one.

    The following likes to be in a file called "permutation.py" for __main__
    to work. A couple of lines went over 80 characters, so you might have to
    put those back together.

    -Jim Washington

    """ ***Reversible*** Permutations using factoradics.

    factoradic concept at:

    http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnnetsec/html/permutations.asp

    Why permutations? Sometimes, you need to list your objects in a different order.
    Maybe, when you are dealing with something persistent like Zope, you wish
    your users to access things in a different order than other users. Think
    quizzes or photo galleries.

    You think you want randomness, but what you really want is that different users
    get different orderings of things, so that the first item is likely different
    for each individual. But you do not really want randomness; you want a
    particular user always to get the same ordering.

    One way would be to store for each individual the complete list in order,
    This is another way that allows you to just store an index that refers to a
    particular ordering.

    For a list of n items, there are n factorial (n!) possible permutations. So,
    any number from 0 to n!-1 is a valid index to a unique ordering.

    If you have

    foo = Permutation(['a','Fred',23,None])

    the possible indices are numbered 0 to 23 (0 to 4!-1)

    sam = foo.permutation(10)
    mary = foo.permutation(4)

    sam is ['Fred', None, 'a', 23]
    mary is ['a', None,'Fred', 23]

    An interesting thing about the factoradic method is its reversibility.

    If you have a list: ['a','Fred',23,None]

    and you are presented with an ordering: [23,'a',None,'Fred']
    the factoradic method can algorithmically determine that this ordering is
    index 13 of 24 of the possible permutations, without going forward through
    your generating algorithm to get there.

    foo = Permutation(['a','Fred',23,None])
    ix = foo.getPermutationIndex([23,'a',None,'Fred'])

    ix is 13.

    For the above example, I used a list of mixed items; you probably will not.
    Reversibility does not work if items are repeated, since it cannot know the
    original positions of repeated items. If you have duplicated items, use their
    list index instead of the items themselves.

    """
    try:
    import psyco
    psyco.full()
    except:
    pass

    import random


    def factoradic(anInt,order=0):
    """calculate the factoradic on anInt

    >>> factoradic(859)

    [1, 1, 0, 3, 0, 1, 0]

    >>> factoradic(11233111122213455539988899978655326328)

    [1, 9, 22, 2, 20, 20, 7, 14, 0, 19, 2, 13, 2, 5, 14, 18, 2, 0, 10, 1, 9, 3, 11, 9, 9, 4, 1, 4, 0, 0, 1, 1, 0, 0]

    >>> factoradic(0,4)

    [0, 0, 0, 0]

    >>> factoradic(1)

    [1, 0]

    >>> factoradic(1047)

    [1, 2, 3, 2, 1, 1, 0]

    >>> factoradic(5,4)

    [0, 2, 1, 0]


    """

    factoradic = []

    z = 0
    while anInt > 0:
    z += 1
    factoradic.append(int(anInt % z))
    anInt /= z


    factoradic.reverse()
    if order:
    while len(factoradic) < order:
    factoradic.insert(0,0)

    return factoradic

    def factorial(anInt):
    """factorial

    >>> factorial(3)

    6
    >>> factorial(0)

    1
    >>> factorial(1)

    1
    """
    if anInt == 0:
    return 1
    if anInt < 0:
    raise ValueError, "Cannot factorialize negative numbers"
    result = 1

    while anInt > 1:
    result = result * anInt
    anInt -= 1
    return result


    def unfactoradic(aList):
    """from a factoradic list, calculate the integer

    >>> unfactoradic([1, 1, 0, 3, 0, 1, 0])

    859

    """
    aList.reverse()
    result = 0
    for idx,val in enumerate(aList):
    result += factorial(idx) * val
    return result



    class Permutation(object):
    """Base object for doing permutations. Generally initialized with a list
    of the items to do permutations on. Works by the factoradic method,
    which provides reversibility."""

    _order = None

    def __init__(self,data):
    self.data = data

    def getOrder(self):
    if not self._order:
    self._order = len(self.data)
    return self._order

    def permutationIndices(self,anInt):
    """calculate the permutation indices of self from anInt

    >>> z = Permutation([1,2,3,4,5,6,7])
    >>> z.permutationIndices(1047)

    [1, 3, 5, 4, 2, 6, 0]
    >>> z = Permutation([0,1,2,3])
    >>> z.permutationIndices(5)

    [0, 3, 2, 1]


    """
    f = factoradic(anInt,self.order)
    temp = []
    for k in f:
    temp.append(k + 1)

    data = [1]
    temp.reverse()
    for k in temp[1:]:
    data.insert(0,k)
    for idx,val in enumerate(data[1:]):
    if val >= k:
    data[idx+1] = val + 1
    for idx,val in enumerate(data):
    data[idx] = val-1
    return data


    def permutation(self,anInt):
    """return a list of permutated items

    >>> z = Permutation([1,2,3,4,5,6,7])
    >>> z.permutation(1047)

    [2, 4, 6, 5, 3, 7, 1]

    """
    indices = self.permutationIndices(anInt)
    newlist = []
    for k in indices:
    newlist.append(self.data[k])
    return newlist

    def randomPermutation(self):
    """just get one of them, randomly"""
    r = random.randint(0,factorial(self.order))
    return self.permutation(r)

    def getPermutationIndex(self,aPermutation):
    """presuming a unique list, get the permutation index of the given
    permutation list.

    >>> d = [1,2,3,4,5,6,7]
    >>> z = Permutation(d)
    >>> z.getPermutationIndex([2, 4, 6, 5, 3, 7, 1])

    1047
    """
    indexkey = []
    for k in aPermutation:
    indexkey.append(self.data.index(k))
    data = []
    for k in indexkey:
    data.append(k+1)
    factoradic = []
    while len(data) > 0:
    r = data.pop(0)
    factoradic.append(r-1)
    for idx,val in enumerate(data):
    if val >= r:
    data[idx] = val -1
    return unfactoradic(factoradic)

    order = property(getOrder)

    def listAll(anInt):
    theList = []
    for k in range(anInt):
    theList.append(k)
    z = Permutation(theList)
    for k in range(factorial(len(z.data))):
    b = factoradic(k,len(z.data))
    c = z.permutation(k)
    d = z.getPermutationIndex(c)
    print "%s\t%s\t%s\t%s" % (k,b,c,d)


    def _test():
    import doctest,permutation
    return doctest.testmod(permutation)


    if __name__ == '__main__':
    _test()
    listAll(4)
    Jim Washington, Aug 14, 2005
    #5
  6. 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
    Jack Diederich, Aug 14, 2005
    #6
  7. 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
    Casey Hawthorne, Aug 14, 2005
    #7
  8. Talin

    David Isaac Guest

    "Casey Hawthorne" <> wrote in message
    news:...
    > 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.
    David Isaac, Aug 14, 2005
    #8
  9. Talin

    Matt Hammond Guest

    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 ] + 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.
    Matt Hammond, Aug 15, 2005
    #9
  10. Talin

    Tom Anderson Guest

    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.
    Tom Anderson, Aug 15, 2005
    #10
  11. 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[0]
    value = self.__current[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[1] > mobile:
    self.__current[0] = -self.__current[0]




    x = NPermutation( 6 )

    print 'loop with __getitem__'
    print '---------------'
    for i in range( x.count ):
    print x

    print 'loop with __iter__'
    print '---------------'
    for perm in x:
    print perm


    Gerard Flanagan

    15/8/05
    Gerard Flanagan, Aug 15, 2005
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roger B.
    Replies:
    13
    Views:
    596
    D.F.S.
    Sep 26, 2003
  2. m sergei
    Replies:
    4
    Views:
    11,096
    Philip Parker
    Jun 29, 2004
  3. Sriram Rajagopalan

    String Permutation function in C

    Sriram Rajagopalan, Oct 29, 2003, in forum: C Programming
    Replies:
    7
    Views:
    13,145
  4. robert
    Replies:
    2
    Views:
    592
  5. Replies:
    14
    Views:
    1,380
    Jorgen Grahn
    Nov 4, 2008
Loading...

Share This Page