some sort of permutations...

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

 

[Fredrik Lundh]

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/Cookbook/Python/Recipe/190465

</F>

 

[Bill Mill]

did you try googling for "python permutations" ?

here's the first hit:

http://aspn.activestate.com/ASPN/Cookbook/Python/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

 

[Scott David Daniels]

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
(e-mail address removed)

 

[Jack Diederich]

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