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