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:
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
--
http://mail.python.org/mailman/listinfo/python-list
