new itertools functions in Python 2.6

Discussion in 'Python' started by Mensanator, Jul 14, 2008.

  1. Mensanator

    Mensanator Guest

    With the new functions added to itertools in Python 2.6,
    I can finally get rid of this monstrosity:

    def ooloop6(a, n, perm=True, repl=True):
    if (not repl) and (n>len(a)): return
    r0 = range(n)
    r1 = r0[1:]
    if perm and repl: # ok
    v = ','.join(['c%s' % i for i in r0])
    f = ' '.join(['for c%s in a' % i for i in r0])
    e = ''.join(["p = [''.join((",v,")) ",f,"]"])
    exec e
    return p
    if (not perm) and repl: # ok
    v = ','.join(['c%s' % i for i in r0])
    f = ' '.join(['for c%s in a' % i for i in r0])
    i = ' and '.join(['(c%s>=c%s)' % (j,j-1) for j in r1])
    e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"])
    exec e
    return p
    if perm and (not repl): # ok
    v = ','.join(['c%s' % i for i in r0])
    f = ' '.join(['for c%s in a' % i for i in r0])
    i = ' and '.join([' and '.join(['(c%s!=c%s)' % (j,k) for k in
    range(j)]) for j in r1])
    e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"])
    exec e
    return p
    if (not perm) and (not repl): # ok
    v = ','.join(['c%s' % i for i in r0])
    f = ' '.join(['for c%s in a' % i for i in r0])
    i = ' and '.join(['(c%s>c%s)' % (j,j-1) for j in r1])
    e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"])
    exec e
    return p

    If I use a single iterable with the repeat option,
    the Carteisan Product will give me Permutaions With Replacement.

    from itertools import *
    from math import factorial as fac

    s = 'abcde'
    m = len(s)
    n = 3

    print 'For %d letters (%s) taken %d at a time:' % (m,s,n)
    print '========================================'

    ### Permutations with replacement m**n
    ###
    print 'Permutations with replacement'
    print '-----------------------------'
    p = [i for i in product('abcde',repeat=3)]
    for i in p:
    print ''.join(i),
    print
    print
    print 'actual words: %d m**n words: %d' % (len(p),m**n)
    print

    ## For 5 letters (abcde) taken 3 at a time:
    ## ========================================
    ## Permutations with replacement
    ## -----------------------------
    ## aaa aab aac aad aae aba abb abc abd abe aca acb
    ## acc acd ace ada adb adc add ade aea aeb aec aed
    ## aee baa bab bac bad bae bba bbb bbc bbd bbe bca
    ## bcb bcc bcd bce bda bdb bdc bdd bde bea beb bec
    ## bed bee caa cab cac cad cae cba cbb cbc cbd cbe
    ## cca ccb ccc ccd cce cda cdb cdc cdd cde cea ceb
    ## cec ced cee daa dab dac dad dae dba dbb dbc dbd
    ## dbe dca dcb dcc dcd dce dda ddb ddc ddd dde dea
    ## deb dec ded dee eaa eab eac ead eae eba ebb ebc
    ## ebd ebe eca ecb ecc ecd ece eda edb edc edd ede
    ## eea eeb eec eed eee
    ##
    ## actual words: 125 m**n words: 125


    So what does "permutaions" mean in itertools?
    It actually means Permutions Without Replacement.

    ### Permutations without replacement m!/(m-n)!
    ###
    print 'Permutations without replacement'
    print '--------------------------------'
    p = [i for i in permutations('abcde',3)]
    for i in p:
    print ''.join(i),
    print
    print
    print 'actual words: %d m!/(m-n)! words: %d' % (len(p),fac(m)/fac(m-
    n))
    print

    ## Permutations without replacement
    ## --------------------------------
    ## abc abd abe acb acd ace adb adc ade aeb aec aed
    ## bac bad bae bca bcd bce bda bdc bde bea bec bed
    ## cab cad cae cba cbd cbe cda cdb cde cea ceb ced
    ## dab dac dae dba dbc dbe dca dcb dce dea deb dec
    ## eab eac ead eba ebc ebd eca ecb ecd eda edb edc
    ##
    ## actual words: 60 m!/(m-n)! words: 60


    Not surprisingly, "combinations" actually means
    Combinations Without Replacement.

    ### Combinations without replacement m!/(n!(m-n)!)
    ###
    print 'Combinations without replacement'
    print '--------------------------------'
    p = [i for i in combinations('abcde',3)]
    for i in p:
    print ''.join(i),
    print
    print
    print 'actual words: %d m!/(n!(m-n)!) words: %d' % (len(p),fac(m)/
    (fac(n)*factorial(m-n)))
    print

    ## Combinations without replacement
    ## --------------------------------
    ## abc abd abe acd ace ade bcd bce bde cde
    ##
    ## actual words: 10 m!/(n!(m-n)!) words: 10


    Hmm...that's only three subsets of the Cartesian Product.
    No Combinations With Replacement.

    Although you can always filter the Cartesian Product to
    get a subset.

    # Combinations with replacement (m+n-1)!/(n!(m-1)!)
    #
    print 'Combinations with replacement'
    print '-----------------------------'
    p = [i for i in ifilter(lambda x:
    list(x)==sorted(x),product('abcde',repeat=3))]
    for i in p:
    print ''.join(i),
    print
    print
    print 'actual words: %d (m+n-1)!/(n!(m-1)!) words: %d' %
    (len(p),fac(m+n-1)/(fac(n)*fac(m-1)))
    print

    ## Combinations with replacement
    ## -----------------------------
    ## aaa aab aac aad aae abb abc abd abe acc acd ace
    ## add ade aee bbb bbc bbd bbe bcc bcd bce bdd bde
    ## bee ccc ccd cce cdd cde cee ddd dde dee eee
    ##
    ## actual words: 35 (m+n-1)!/(n!(m-1)!) words: 35


    Although it works, it's somewhat slow as we have to iterate
    over the entire Cartesian Product and the filter list(x)==sorted(x)
    has got to be expensive (it's slower than the nested loop algorithm).

    Is there a better way to get Combinations With Replacement
    using itertools?
    Mensanator, Jul 14, 2008
    #1
    1. Advertising

  2. On Jul 14, 1:26 pm, Mensanator <> wrote:
    > ##  Combinations with replacement
    > ##  -----------------------------
    > ##  aaa aab aac aad aae abb abc abd abe acc acd ace
    > ##  add ade aee bbb bbc bbd bbe bcc bcd bce bdd bde
    > ##  bee ccc ccd cce cdd cde cee ddd dde dee eee
    > ##
    > ##  actual words: 35    (m+n-1)!/(n!(m-1)!) words: 35
    >
    > Although it works, it's somewhat slow as we have to iterate
    > over the entire Cartesian Product and the filter list(x)==sorted(x)
    > has got to be expensive (it's slower than the nested loop algorithm).
    >
    > Is there a better way to get Combinations With Replacement
    > using itertools?


    There may a technique to start with the combinations without
    replacement and then grow the result by repeating elements:

    result = set(combinations('abcde', 3))
    # transform 'ab ac ad ae bc bd be cd ce de' into 'aab abb aac
    acc ...'
    for c in combinations('abcde', 2):
    # transform 'ab' --> 'aab abb'
    for i in range(2):
    result.add(c[:i] + c*1 + c[i:])
    for c in combinations('abcde', 1):
    for i in range(1):
    # 'a' --> 'aaa'
    result.add(c[:i] + c*2 + c[i:])

    If you generalize the above, it may solve the problem using itertools
    as a starting point.

    Alternatively, it's not too hard to transform the pure python version
    given in the docs to one that supports combinations with replacement:

    def combinations_with_replacement(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    indices = [0] * r
    yield tuple(pool for i in indices)
    while 1:
    for i in reversed(range(r)):
    if indices != n - 1:
    break
    else:
    return
    indices += 1
    for j in range(i+1, r):
    indices[j] = indices[j-1]
    yield tuple(pool for i in indices)


    Raymond
    Raymond Hettinger, Jul 15, 2008
    #2
    1. Advertising

  3. Mensanator

    Mensanator Guest

    On Jul 15, 1:44 am, Raymond Hettinger <> wrote:
    > On Jul 14, 1:26 pm, Mensanator <> wrote:
    >
    > > ## Combinations with replacement
    > > ## -----------------------------
    > > ## aaa aab aac aad aae abb abc abd abe acc acd ace
    > > ## add ade aee bbb bbc bbd bbe bcc bcd bce bdd bde
    > > ## bee ccc ccd cce cdd cde cee ddd dde dee eee
    > > ##
    > > ## actual words: 35 (m+n-1)!/(n!(m-1)!) words: 35

    >
    > > Although it works, it's somewhat slow as we have to iterate
    > > over the entire Cartesian Product and the filter list(x)==sorted(x)
    > > has got to be expensive (it's slower than the nested loop algorithm).

    >
    > > Is there a better way to get Combinations With Replacement
    > > using itertools?

    >
    > There may a technique to start with the combinations without
    > replacement and then grow the result by repeating elements:


    Great idea, I had only considered making a sub=set. It never
    occured to me to try and make a super=set.

    Thanks for the suggestions, they've given me some
    ideas to try.

    >
    > result = set(combinations('abcde', 3))
    > # transform 'ab ac ad ae bc bd be cd ce de' into 'aab abb aac
    > acc ...'
    > for c in combinations('abcde', 2):
    > # transform 'ab' --> 'aab abb'
    > for i in range(2):
    > result.add(c[:i] + c*1 + c[i:])
    > for c in combinations('abcde', 1):
    > for i in range(1):
    > # 'a' --> 'aaa'
    > result.add(c[:i] + c*2 + c[i:])
    >
    > If you generalize the above, it may solve the problem using itertools
    > as a starting point.
    >
    > Alternatively, it's not too hard to transform the pure python version
    > given in the docs to one that supports combinations with replacement:


    I was trying to avoid that kind of solution.

    ifilter(product()) is exactly the kind of thing
    I'm looking for, just wondering if there's a
    better way, using a different combination of
    functions.

    >
    > def combinations_with_replacement(iterable, r):
    > pool = tuple(iterable)
    > n = len(pool)
    > indices = [0] * r
    > yield tuple(pool for i in indices)
    > while 1:
    > for i in reversed(range(r)):
    > if indices != n - 1:
    > break
    > else:
    > return
    > indices += 1
    > for j in range(i+1, r):
    > indices[j] = indices[j-1]
    > yield tuple(pool for i in indices)
    >
    > Raymond
    Mensanator, Jul 16, 2008
    #3
  4. On Jul 16, 7:20 am, Mensanator <> wrote:
    > > > ##  Combinations with replacement
    > > > ##  -----------------------------
    > > > ##  aaa aab aac aad aae abb abc abd abe acc acd ace
    > > > ##  add ade aee bbb bbc bbd bbe bcc bcd bce bdd bde
    > > > ##  bee ccc ccd cce cdd cde cee ddd dde dee eee
    > > > ##
    > > > ##  actual words: 35    (m+n-1)!/(n!(m-1)!) words: 35


    >>> for x in combinations(range(7), 4):

    ... x = [-1] + list(x) + [7]
    ... print ''.join(c*(x[i+1]-x-1) for i, c in
    enumerate('abcde'))
    ...
    eee
    dee
    dde
    ddd
    cee
    cde
    cdd
    cce
    ccd
    ccc
    bee
    bde
    bdd
    bce
    bcd
    bcc
    bbe
    bbd
    bbc
    bbb
    aee
    ade
    add
    ace
    acd
    acc
    abe
    abd
    abc
    abb
    aae
    aad
    aac
    aab
    aaa


    Generalization left as an exercise for the reader.

    Mark
    Mark Dickinson, Jul 16, 2008
    #4
  5. Mensanator

    Mensanator Guest

    On Jul 16, 5:05 am, Mark Dickinson <> wrote:
    > On Jul 16, 7:20 am, Mensanator <> wrote:
    >
    > > > > ## Combinations with replacement
    > > > > ## -----------------------------
    > > > > ## aaa aab aac aad aae abb abc abd abe acc acd ace
    > > > > ## add ade aee bbb bbc bbd bbe bcc bcd bce bdd bde
    > > > > ## bee ccc ccd cce cdd cde cee ddd dde dee eee
    > > > > ##
    > > > > ## actual words: 35 (m+n-1)!/(n!(m-1)!) words: 35


    > >>> for x in combinations(range(7), 4):

    > ... x = [-1] + list(x) + [7]
    > ... print ''.join(c*(x[i+1]-x-1) for i, c in enumerate('abcde'))


    <snip printout>

    >
    > Generalization left as an exercise for the reader.


    First part of exercise: figure out what's going on.

    ##[-1, 0, 1, 2, 3, 7] ['', '', '', '', 'eee'] eee
    ##[-1, 0, 1, 2, 4, 7] ['', '', '', 'd', 'ee'] dee
    ##[-1, 0, 1, 2, 5, 7] ['', '', '', 'dd', 'e'] dde
    ##[-1, 0, 1, 2, 6, 7] ['', '', '', 'ddd', ''] ddd
    ##[-1, 0, 1, 3, 4, 7] ['', '', 'c', '', 'ee'] cee
    ##[-1, 0, 1, 3, 5, 7] ['', '', 'c', 'd', 'e'] cde
    ##[-1, 0, 1, 3, 6, 7] ['', '', 'c', 'dd', ''] cdd
    ##[-1, 0, 1, 4, 5, 7] ['', '', 'cc', '', 'e'] cce
    ##[-1, 0, 1, 4, 6, 7] ['', '', 'cc', 'd', ''] ccd
    ##[-1, 0, 1, 5, 6, 7] ['', '', 'ccc', '', ''] ccc
    ## Damn, that's clever
    ## empty strings disappear when joined

    Here's what I came with for a generalization.


    s = 'abcde'
    m = len(s)
    n = 3
    mn1 = m+n-1
    m1 = m-1

    p = [tuple(''.join(c*(q[i+1]-q-1) for i, c in enumerate(s))) \
    for q in [[t for t in chain.from_iterable(([-1],r,[mn1]))] \
    for r in combinations(range(mn1), m1)]]

    I used the tuple() to give output consistent with the itertools
    functions.

    Combinations with replacement
    [26 letters 4 at a time]
    version 2 (Mark Dickinson)
    -------------------------------------------------------
    actual words: 23751 (m+n-1)!/(n!(m-1)!) words: 23751
    0.828000068665 seconds

    Drat, that's not very impressive.

    And here I thought using chain.from_iterable was a nice touch.

    Not much better than my version.

    p = [i for i in ifilter(lambda x:
    list(x)==sorted(x),product(s,repeat=n))]

    Combinations with replacement
    [26 letters 4 at a time]
    (using ifilter(product))
    -------------------------------------------------------
    actual words: 23751 (m+n-1)!/(n!(m-1)!) words: 23751
    0.84299993515 seconds

    Maybe all the time saved not iterating through the entire
    Cartesian Product is lost to the overhead of all that list
    and string manipulation. Makes me wish they had done this
    function directly in itertools.

    Even the full Cartesian Product is faster despite being
    almost 20 times larger:

    Permutations with replacement
    [26 letters 4 at a time]
    (using product)
    -------------------------------------------------------
    0.453000068665 seconds for 456976 words

    Not to mention my goofy ooloop6 program (which certainly
    isn't a replacement for itertools since it only works with
    a single sorted iterable).

    Combinations with replacement
    [26 letters 4 at a time]
    original nested for loop
    -------------------------------------------------------
    0.18700003624 seconds for 23751 words

    Permutations with replacement
    [26 letters 4 at a time]
    original nested for loop
    -------------------------------------------------------
    0.344000101089 seconds for 456976 words

    So, maybe there simply ISN'T a GOOD way to do Combinations
    With Replacement.

    Thanks anyway.

    >
    > Mark
    Mensanator, Jul 19, 2008
    #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. Replies:
    0
    Views:
    860
  2. Steven Bethard
    Replies:
    0
    Views:
    384
    Steven Bethard
    Mar 12, 2005
  3. John Reese
    Replies:
    10
    Views:
    563
    Carl Banks
    Nov 14, 2006
  4. Raymond Hettinger
    Replies:
    17
    Views:
    533
    Simon Brunning
    Feb 18, 2008
  5. Nick Mellor
    Replies:
    35
    Views:
    337
    Paul Rubin
    Dec 6, 2012
Loading...

Share This Page