Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   combinatorics via __future__ generators (http://www.velocityreviews.com/forums/t705816-combinatorics-via-__future__-generators.html)

 Phlip 11-19-2009 12:58 AM

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/

 Phlip 11-19-2009 01:07 AM

Re: combinatorics via __future__ generators

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/

 Chris Rebert 11-19-2009 02:42 AM

Re: combinatorics via __future__ generators

On Wed, Nov 18, 2009 at 4:58 PM, Phlip <phlip2005@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, 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

 Phlip 12-01-2009 10:55 PM

Re: combinatorics via __future__ generators

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...

 John Yeung 12-02-2009 05:35 AM

Re: combinatorics via __future__ generators

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

 All times are GMT. The time now is 06:28 PM.