new itertools functions in Python 2.6

[Mensanator]

On Jul 16, 5:05 am, Mark Dickinson <dicki... at gmail.com> wrote:
> On Jul 16, 7:20 am, Mensanator <mensana... at aol.com> 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[i]-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[i]-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