combinatorics via __future__ generators

Discussion in 'Python' started by Phlip, Nov 19, 2009.

  1. Phlip

    Phlip Guest

    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, Nov 19, 2009
    #1
    1. Advertising

  2. Phlip

    Phlip Guest

    On Nov 18, 4:58 pm, Phlip <> 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/
    Phlip, Nov 19, 2009
    #2
    1. Advertising

  3. Phlip

    Chris Rebert Guest

    On Wed, Nov 18, 2009 at 4:58 PM, Phlip <> 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
    Chris Rebert, Nov 19, 2009
    #3
  4. Phlip

    Phlip Guest

    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...
    Phlip, Dec 1, 2009
    #4
  5. Phlip

    John Yeung Guest

    On Dec 1, 5:55 pm, Phlip <> 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
    John Yeung, Dec 2, 2009
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Carnosaur

    combinatorics question

    Carnosaur, Oct 28, 2003, in forum: C Programming
    Replies:
    17
    Views:
    544
    Carnosaur
    Oct 31, 2003
  2. Xah Lee

    [perl-python] combinatorics fun

    Xah Lee, Feb 10, 2005, in forum: Python
    Replies:
    7
    Views:
    382
    bruno modulix
    Feb 11, 2005
  3. Nic

    Python and Combinatorics

    Nic, May 16, 2006, in forum: Python
    Replies:
    4
    Views:
    1,712
    Gerard Flanagan
    May 16, 2006
  4. none

    Python and Combinatorics

    none, Oct 24, 2007, in forum: Python
    Replies:
    4
    Views:
    477
    Gerard Flanagan
    Oct 26, 2007
  5. Michael Robertson

    Combinatorics

    Michael Robertson, Feb 12, 2008, in forum: Python
    Replies:
    12
    Views:
    909
    Paul Hankin
    Feb 13, 2008
Loading...

Share This Page