Mailing List Archive: Python: Python

combinatorics via future generators

Index | Next | Previous | View Threaded

phlip2005 at gmail

Nov 18, 2009, 4:58 PM

Post #1 of 5 (223 views)
Permalink

combinatorics via __future__ generators

Python:

I have a quaint combinatorics problem. Before I solve it, or find a
solution among "generators", I thought y'all might like to show off
any solutions.

Given an array like this...

[0, 4, 3]

Produce an array like this:

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

The first array is the counts of options in 4 slots, and the second is
all combinations of indexes of each option, such that every option
associates once with every other option. The leading 0 simply
represents a slot with no options; the algorithm must preserve those.

This should be child's play for the generator package, right?

--
Phlip
http://zeekland.zeroplayer.com/
--
http://mail.python.org/mailman/listinfo/python-list

phlip2005 at gmail

Nov 18, 2009, 5:07 PM

Post #2 of 5 (224 views)
Permalink

Re: combinatorics via __future__ generators [In reply to]

On Nov 18, 4:58 pm, Phlip <phlip2...@gmail.com> wrote:
> Python:
>
> I have a quaint combinatorics problem. Before I solve it, or find a
> solution among "generators", I thought y'all might like to show off
> any solutions.
>
> Given an array like this...
>
> [0, 4, 3]
>
> Produce an array like this:
>
> [
> [0, 0, 0],
> [0, 1, 0],
> [0, 2, 0],
> [0, 3, 0],
[0, 0, 1],
> [0, 1, 1],
> [0, 2, 1],
> [0, 3, 1],
[0, 0, 2],
> [0, 1, 2],
> [0, 2, 2],
> [0, 3, 2],
> ]

I forgot those combinations!

>
> The first array is the counts of options in 4 slots, and the second is
> all combinations of indexes of each option, such that every option
> associates once with every other option. The leading 0 simply
> represents a slot with no options; the algorithm must preserve those.
>
> This should be child's play for the generator package, right?
>
> --
> Phlip
> http://zeekland.zeroplayer.com/

--
http://mail.python.org/mailman/listinfo/python-list

clp2 at rebertia

Nov 18, 2009, 6:42 PM

Post #3 of 5 (219 views)
Permalink

Re: combinatorics via __future__ generators [In reply to]

On Wed, Nov 18, 2009 at 4:58 PM, Phlip <phlip2005 [at] gmail> wrote:
> Python:
>
> I have a quaint combinatorics problem. Before I solve it, or find a
> solution among "generators", I thought y'all might like to show off
> any solutions.
>
> Given an array like this...
>
> Ā [0, 4, 3]
>
> Produce an array like this:
>
> Ā [
> Ā Ā [0, 0, 0],
> Ā Ā [0, 1, 0],
> Ā Ā [0, 2, 0],
> Ā Ā [0, 3, 0],
> Ā Ā [0, 1, 1],
> Ā Ā [0, 2, 1],
> Ā Ā [0, 3, 1],
> Ā Ā [0, 1, 2],
> Ā Ā [0, 2, 2],
> Ā Ā [0, 3, 2],
> ]
>
> The first array is the counts of options in 4 slots, and the second is
> all combinations of indexes of each option, such that every option
> associates once with every other option. The leading 0 simply
> represents a slot with no options; the algorithm must preserve those.
>
> This should be child's play for the generator package, right?

from itertools import imap, product

def special_range(n):
return (xrange(n) if n else [0])

def something(arr):
return product(*imap(special_range, arr))

print list(something([0,4,3]))

Cheers,
Chris
--
http://blog.rebertia.com
--
http://mail.python.org/mailman/listinfo/python-list

phlip2005 at gmail

Dec 1, 2009, 2:55 PM

Post #4 of 5 (159 views)
Permalink

Re: combinatorics via __future__ generators [In reply to]

Awesome thanks - but:

> from itertools import imap,product

Do we have a version for Python2.5? I have to support an older server
here; can't install a newer python on it...

--
http://mail.python.org/mailman/listinfo/python-list

gallium.arsenide at gmail

Dec 1, 2009, 9:35 PM

Post #5 of 5 (158 views)
Permalink

Re: combinatorics via __future__ generators [In reply to]

On Dec 1, 5:55 pm, Phlip <phlip2...@gmail.com> wrote:
> Awesome thanks - but:
>
> > from itertools import imap,product
>
> Do we have a version for Python2.5? I have to support an older server
> here; can't install a newer python on it...

If you can get by with the performance of pure Python, a solution is
right in the documentation for 2.6:

###
def product(*args, **kwds):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = map(tuple, args) * kwds.get('repeat', 1)
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
###

The docs for itertools are full of these definitions (for 2.6
functions) that can be used as recipes (if you don't have 2.6).

John
--
http://mail.python.org/mailman/listinfo/python-list

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads

combinatorics via __future__ generators

combinatorics via future generators