On Jul 16, 5:05 am, Mark Dickinson <[EMAIL PROTECTED]> wrote:
> On Jul 16, 7:20 am, 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
> >>> for x in combinations(range(7), 4):
> ... x = [-1] + list(x) + [7]
> ... print ''.join(c*(x[i+1]-x[i]-1) for i, c in enumerate('abcde'))
<snip printout>
>
> 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[i]-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.
>
> Mark
--
http://mail.python.org/mailman/listinfo/python-list
