Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Permutation Generator

Reply
Thread Tools

Permutation Generator

 
 
Talin
Guest
Posts: n/a
 
      08-12-2005
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
 
Reply With Quote
 
 
 
 
Michael J. Fromberger
Guest
Posts: n/a
 
      08-12-2005
In article <(E-Mail Removed)>,
Talin <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Paul Rubin
Guest
Posts: n/a
 
      08-12-2005
Talin <(E-Mail Removed)> 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.
 
Reply With Quote
 
David Isaac
Guest
Posts: n/a
 
      08-13-2005
"Talin" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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


 
Reply With Quote
 
Jim Washington
Guest
Posts: n/a
 
      08-13-2005
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/de...rmutations.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(1123311112221345553998889997865532632

[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)


 
Reply With Quote
 
Jack Diederich
Guest
Posts: n/a
 
      08-14-2005
On Fri, Aug 12, 2005 at 03:48:38PM -0400, Michael J. Fromberger wrote:
> In article <(E-Mail Removed)>,
> Talin <(E-Mail Removed)> 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
 
Reply With Quote
 
Casey Hawthorne
Guest
Posts: n/a
 
      08-14-2005
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
 
Reply With Quote
 
David Isaac
Guest
Posts: n/a
 
      08-14-2005

"Casey Hawthorne" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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.


 
Reply With Quote
 
Matt Hammond
Guest
Posts: n/a
 
      08-15-2005
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
<(E-Mail Removed)> wrote:

> In article <(E-Mail Removed)>,
> Talin <(E-Mail Removed)> 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.
 
Reply With Quote
 
Tom Anderson
Guest
Posts: n/a
 
      08-15-2005
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Unyeilding a permutation generator sillyhat@yahoo.com Python 14 11-04-2008 07:27 PM
n-dim permutation matrix/generator? robert Python 2 11-20-2006 05:13 PM
algorithm for finding permutation of characters m sergei C++ 4 06-29-2004 08:04 AM
String Permutation function in C Sriram Rajagopalan C Programming 7 10-30-2003 08:18 PM
Permutation lists?? Really Need Help Roger B. C++ 13 09-26-2003 02:21 AM



Advertisments