new itertools functions in Python 2.6

[Raymond Hettinger]

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:

   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:

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