By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,587 Members | 1,575 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,587 IT Pros & Developers. It's quick & easy.

some sort of permutations...

P: n/a
hello,

i'm looking for a way to have all possible length fixed n-uples from a
list, i think generators can help, but was not able to do it myself,
maybe some one could point me out to an idea to do it ?

for example, from :
l = [0, 1, 2, 3, 4]

and searching for n-uples of 3, i should produce :
(
(0, 1, 2),
(0, 1, 3),
(0, 1, 4),
(0, 2, 3),
(0, 2, 4),
(0, 3, 4),
(1, 2, 3),
(1, 2, 4),
(1, 3, 4),
(2, 3, 4),
)

does the set module or itertools can help in such cases ? i still have
missed the black magic behind itertools...

best regards
Jul 18 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
"Bernard A." wrote:
i'm looking for a way to have all possible length fixed n-uples from a
list, i think generators can help, but was not able to do it myself,
maybe some one could point me out to an idea to do it ?


did you try googling for "python permutations" ?

here's the first hit:

http://aspn.activestate.com/ASPN/Coo.../Recipe/190465

</F>

Jul 18 '05 #2

P: n/a
On Apr 12, 2005 2:37 AM, Fredrik Lundh <fr*****@pythonware.com> wrote:
"Bernard A." wrote:
i'm looking for a way to have all possible length fixed n-uples from a
list, i think generators can help, but was not able to do it myself,
maybe some one could point me out to an idea to do it ?


did you try googling for "python permutations" ?

here's the first hit:

http://aspn.activestate.com/ASPN/Coo.../Recipe/190465


I've used that recipe a significant amount, and I feel like its
recursion really slows it down (but I haven't been profiled it). Does
anyone know of a non-recursive algorithm to do the same thing?

And, while I'm asking that question, is there a good reference for
finding such algorithms? Do most people keep an algorithms book handy?

Peace
Bill Mill
bill.mill at gmail.com
Jul 18 '05 #3

P: n/a
Bill Mill wrote:
On Apr 12, 2005 2:37 AM, Fredrik Lundh <fr*****@pythonware.com> wrote:
"Bernard A." wrote:
i'm looking ... to have all possible length fixed n-uples from a list...

... http://aspn.activestate.com/ASPN/Coo.../Recipe/190465

And, while I'm asking that question, is there a good reference for
finding such algorithms? Do most people keep an algorithms book handy?

Volume 4 of Knuth's TAOCP (The Art of Computer Programming) is about
combinatorics. Fascicle 2 is out and relevant. Admittedly buying
fascicles is a bit like buying a long chapter at a time, but it is
chock-a-block with great stuff. I paid about twenty bucks a fascicle.

--Scott David Daniels
Sc***********@Acm.Org
Jul 18 '05 #4

P: n/a
On Tue, Apr 12, 2005 at 08:41:15AM -0400, Bill Mill wrote:
On Apr 12, 2005 2:37 AM, Fredrik Lundh <fr*****@pythonware.com> wrote:
"Bernard A." wrote:
i'm looking for a way to have all possible length fixed n-uples from a
list, i think generators can help, but was not able to do it myself,
maybe some one could point me out to an idea to do it ?
did you try googling for "python permutations" ?

here's the first hit:

http://aspn.activestate.com/ASPN/Coo.../Recipe/190465


I've used that recipe a significant amount, and I feel like its
recursion really slows it down (but I haven't been profiled it). Does
anyone know of a non-recursive algorithm to do the same thing?


If you need the speed probstat.sf.net has permutations, combinations,
and cartesian products written in C. I'm the author and I use pure-python
versions when I know I'm just doing small lists (to avoid a dependency).
From your original problem it looks like you want a combination, not

a permutation. Combinations don't care about order (just unique sets).
import probstat
for (item) in probstat.Combination([0,1,2,3,4], 3):

.... print item
....
[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

-jackdied
Jul 18 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.