On Jul 15, 1:44 am, Raymond Hettinger <[EMAIL PROTECTED]> wrote:
> On Jul 14, 1:26 pm, Mensanator <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
