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 10 5618
In article <ma************ *************** ************@py thon.org>,
Talin <ta***@acm.or g> 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
Talin <ta***@acm.or g> 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.
"Talin" <ta***@acm.or g> wrote in message
news:ma******** *************** *************** *@python.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
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,N one])
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,N one]
and you are presented with an ordering: [23,'a',None,'Fr ed']
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,N one])
ix = foo.getPermutat ionIndex([23,'a',None,'Fr ed'])
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(anIn t,order=0):
"""calculat e the factoradic on anInt factoradic(859)
[1, 1, 0, 3, 0, 1, 0]
factoradic(1123 311112221345553 998889997865532 6328)
[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.appe nd(int(anInt % z))
anInt /= z
factoradic.reve rse()
if order:
while len(factoradic) < order:
factoradic.inse rt(0,0)
return factoradic
def factorial(anInt ):
"""factoria l
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(aL ist):
"""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(obj ect):
"""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,d ata):
self.data = data
def getOrder(self):
if not self._order:
self._order = len(self.data)
return self._order
def permutationIndi ces(self,anInt) :
"""calculat e the permutation indices of self from anInt
z = Permutation([1,2,3,4,5,6,7]) z.permutationIn dices(1047)
[1, 3, 5, 4, 2, 6, 0] z = Permutation([0,1,2,3]) z.permutationIn dices(5)
[0, 3, 2, 1]
"""
f = factoradic(anIn t,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(sel f,anInt):
"""return a list of permutated items
z = Permutation([1,2,3,4,5,6,7]) z.permutation(1 047)
[2, 4, 6, 5, 3, 7, 1]
"""
indices = self.permutatio nIndices(anInt)
newlist = []
for k in indices:
newlist.append( self.data[k])
return newlist
def randomPermutati on(self):
"""just get one of them, randomly"""
r = random.randint( 0,factorial(sel f.order))
return self.permutatio n(r)
def getPermutationI ndex(self,aPerm utation):
"""presumin g a unique list, get the permutation index of the given
permutation list.
d = [1,2,3,4,5,6,7] z = Permutation(d) z.getPermutatio nIndex([2, 4, 6, 5, 3, 7, 1])
1047
"""
indexkey = []
for k in aPermutation:
indexkey.append (self.data.inde x(k))
data = []
for k in indexkey:
data.append(k+1 )
factoradic = []
while len(data) > 0:
r = data.pop(0)
factoradic.appe nd(r-1)
for idx,val in enumerate(data) :
if val >= r:
data[idx] = val -1
return unfactoradic(fa ctoradic)
order = property(getOrd er)
def listAll(anInt):
theList = []
for k in range(anInt):
theList.append( k)
z = Permutation(the List)
for k in range(factorial (len(z.data))):
b = factoradic(k,le n(z.data))
c = z.permutation(k )
d = z.getPermutatio nIndex(c)
print "%s\t%s\t%s\t%s " % (k,b,c,d)
def _test():
import doctest,permuta tion
return doctest.testmod (permutation)
if __name__ == '__main__':
_test()
listAll(4)
On Fri, Aug 12, 2005 at 03:48:38PM -0400, Michael J. Fromberger wrote: In article <ma************ *************** ************@py thon.org>, Talin <ta***@acm.or g> 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.c om 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
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" <ca************ ***@istar.ca> wrote in message
news:s1******** *************** *********@4ax.c om... 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.
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(li st)):
.... 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
<Mi************ ******@Clothing .Dartmouth.EDU> wrote:
In article <ma************ *************** ************@py thon.org>, Talin <ta***@acm.or g> 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.
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(factoria l(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. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Jack Middleton |
last post by:
Hi!
I'm lookin for a faster permutation algorithm for matrices. I know that
it can be done with multiplying a matrix with a permutation matrix. It
just seems a waste to iterate through all those zeroes. Is there an
algorithm for matrixes that is optimized just for permutations? The
matrices that I use are fairly small (around 6*6) and I only use
positive integers as elements.
Thanks for help,
|
by: user |
last post by:
Hello
I have Array of 50 ints. I want to receive random permutation, so
in each int will be different number from 0-49.
Is there any class for permutation ?
Thanx
Michal
|
by: Rajesh |
last post by:
Hello Everybody,
Can anybody help me in writing a C program to generate and print all
possible combinations of n numbers.
For eg. for 3 numbers(1,2,3) there turn out 3! combinations.
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
|
by: robert |
last post by:
for the purpose of flat n-dim iteration a function or generator ndim_permute(*v) should compute or generate a list of tuples like:
ndim_permute( (0,1,2), (0,1), (0,1), ) ->
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 1
|
by: weidongtom |
last post by:
Hi,
I have been working at this problem, and I think I need a permutation
algorithm that does
the following:
Given a list of elements that are either a character or a character
follows by a number, e.g.
| |
by: badcrusher10 |
last post by:
Hello.
I'm having trouble figuring out what to do and how to do.. could someone explain to me what I need to do in order to work?
THIS IS WHAT I NEED TO DO:
Professor Snoop wants a program that will randomly generate 10 unique random numbers. Your job is to write a program that produces random permutations of the numbers 1 to 10. “Permutation” is a mathematical name for an arrangement. For example, there are six permutations of the...
|
by: xirowei |
last post by:
Let's say i create a String array that store 4 Alphabets {"A","B","C","D"}
How can i get the result if i need permutation of 4P3 and 4P2?
I had refer to many examples from the internet, but those examples cannot compute n selection from m elements. They only able to computer permutation of m elements without selection e.g. 4P4.
Hence i need guideline in how to compute this kind of permutation.
If i use manual calculation of 4P3...
|
by: 249740 |
last post by:
Write a program that reads N phrases and determines if one phrase is a
permutation of the other. For example: Phrase 1 is: “One World One Dream” Phrase 2 is: “World One One Dream”. Then the output should say that phrase 1 is permutation of phrase 2. Note that spaces/tabs are not counted as characters.
Sample Input:
3
One World One Dream
World One One Dream
No World No Dream
Sample Output:
Phrase 1 is permutation of Phrase 2
|
by: sillyhat |
last post by:
Hello, can someone please help.
I found the following code at http://code.activestate.com/recipes/252178/
def all_perms(str):
if len(str) <=1:
yield str
else:
for perm in all_perms(str):
for i in range(len(perm)+1):
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |