new itertools functions in Python 2.6

[Mensanator]

With the new functions added to itertools in Python 2.6,
I can finally get rid of this monstrosity:

def ooloop6(a, n, perm=True, repl=True):
if (not repl) and (n>len(a)): return
r0 = range(n)
r1 = r0[1:]
if perm and repl: # ok
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
e = ''.join(["p = [''.join((",v,")) ",f,"]"])
exec e
return p
if (not perm) and repl: # ok
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
i = ' and '.join(['(c%s>=c%s)' % (j,j-1) for j in r1])
e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"])
exec e
return p
if perm and (not repl): # ok
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
i = ' and '.join([' and '.join(['(c%s!=c%s)' % (j,k) for k in
range(j)]) for j in r1])
e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"])
exec e
return p
if (not perm) and (not repl): # ok
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
i = ' and '.join(['(c%s>c%s)' % (j,j-1) for j in r1])
e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"])
exec e
return p

If I use a single iterable with the repeat option,
the Carteisan Product will give me Permutaions With Replacement.

from itertools import *
from math import factorial as fac

s = 'abcde'
m = len(s)
n = 3

print 'For %d letters (%s) taken %d at a time:' % (m,s,n)
print '========================================'

### Permutations with replacement m**n
###
print 'Permutations with replacement'
print '-----------------------------'
p = [i for i in product('abcde',repeat=3)]
for i in p:
print ''.join(i),
print
print
print 'actual words: %d m**n words: %d' % (len(p),m**n)
print

## For 5 letters (abcde) taken 3 at a time:
## ========================================
## Permutations with replacement
## -----------------------------
## aaa aab aac aad aae aba abb abc abd abe aca acb
## acc acd ace ada adb adc add ade aea aeb aec aed
## aee baa bab bac bad bae bba bbb bbc bbd bbe bca
## bcb bcc bcd bce bda bdb bdc bdd bde bea beb bec
## bed bee caa cab cac cad cae cba cbb cbc cbd cbe
## cca ccb ccc ccd cce cda cdb cdc cdd cde cea ceb
## cec ced cee daa dab dac dad dae dba dbb dbc dbd
## dbe dca dcb dcc dcd dce dda ddb ddc ddd dde dea
## deb dec ded dee eaa eab eac ead eae eba ebb ebc
## ebd ebe eca ecb ecc ecd ece eda edb edc edd ede
## eea eeb eec eed eee
##
## actual words: 125 m**n words: 125


So what does "permutaions" mean in itertools?
It actually means Permutions Without Replacement.

### Permutations without replacement m!/(m-n)!
###
print 'Permutations without replacement'
print '--------------------------------'
p = [i for i in permutations('abcde',3)]
for i in p:
print ''.join(i),
print
print
print 'actual words: %d m!/(m-n)! words: %d' % (len(p),fac(m)/fac(m-
n))
print

## Permutations without replacement
## --------------------------------
## abc abd abe acb acd ace adb adc ade aeb aec aed
## bac bad bae bca bcd bce bda bdc bde bea bec bed
## cab cad cae cba cbd cbe cda cdb cde cea ceb ced
## dab dac dae dba dbc dbe dca dcb dce dea deb dec
## eab eac ead eba ebc ebd eca ecb ecd eda edb edc
##
## actual words: 60 m!/(m-n)! words: 60


Not surprisingly, "combinations" actually means
Combinations Without Replacement.

### Combinations without replacement m!/(n!(m-n)!)
###
print 'Combinations without replacement'
print '--------------------------------'
p = [i for i in combinations('abcde',3)]
for i in p:
print ''.join(i),
print
print
print 'actual words: %d m!/(n!(m-n)!) words: %d' % (len(p),fac(m)/
(fac(n)*factorial(m-n)))
print

## Combinations without replacement
## --------------------------------
## abc abd abe acd ace ade bcd bce bde cde
##
## actual words: 10 m!/(n!(m-n)!) words: 10


Hmm...that's only three subsets of the Cartesian Product.
No Combinations With Replacement.

Although you can always filter the Cartesian Product to
get a subset.

# Combinations with replacement (m+n-1)!/(n!(m-1)!)
#
print 'Combinations with replacement'
print '-----------------------------'
p = [i for i in ifilter(lambda x:
list(x)==sorted(x),product('abcde',repeat=3))]
for i in p:
print ''.join(i),
print
print
print 'actual words: %d (m+n-1)!/(n!(m-1)!) words: %d' %
(len(p),fac(m+n-1)/(fac(n)*fac(m-1)))
print

## 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?

 

[Raymond Hettinger]

##  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*1 + c[i:])
for c in combinations('abcde', 1):
for i in range(1):
# 'a' --> 'aaa'
result.add(c[:i] + c*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 for i in indices)
while 1:
for i in reversed(range(r)):
if indices != n - 1:
break
else:
return
indices += 1
for j in range(i+1, r):
indices[j] = indices[j-1]
yield tuple(pool for i in indices)


Raymond

 

[Mensanator]

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*1 + c[i:])
for c in combinations('abcde', 1):
for i in range(1):
# 'a' --> 'aaa'
result.add(c[:i] + c*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 for i in indices)
while 1:
for i in reversed(range(r)):
if indices != n - 1:
break
else:
return
indices += 1
for j in range(i+1, r):
indices[j] = indices[j-1]
yield tuple(pool for i in indices)

Raymond

 

[Mark Dickinson]

... x = [-1] + list(x) + [7]
... print ''.join(c*(x[i+1]-x-1) for i, c in
enumerate('abcde'))
...
eee
dee
dde
ddd
cee
cde
cdd
cce
ccd
ccc
bee
bde
bdd
bce
bcd
bcc
bbe
bbd
bbc
bbb
aee
ade
add
ace
acd
acc
abe
abd
abc
abb
aae
aad
aac
aab
aaa


Generalization left as an exercise for the reader.

Mark

 

[Mensanator]

... x = [-1] + list(x) + [7]
... print ''.join(c*(x[i+1]-x-1) for i, c in enumerate('abcde'))

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-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.