new itertools functions in Python 2.6

[Mensanator]

On Jul 15, 1:44 am, Raymond Hettinger <pyt... at rcn.com> wrote:
> On Jul 14, 1:26 pm, 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
>
> > 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[i]*1 + c[i:])
>    for c in combinations('abcde', 1):
>        for i in range(1):
>            # 'a' --> 'aaa'
>            result.add(c[:i] + c[i]*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[i] for i in indices)
>     while 1:
>         for i in reversed(range(r)):
>             if indices[i] != n - 1:
>                 break
>         else:
>             return
>         indices[i] += 1
>         for j in range(i+1, r):
>             indices[j] = indices[j-1]
>         yield tuple(pool[i] for i in indices)
>
> Raymond