459,976 Members | 1,593 Online
Need help? Post your question and get tips & solutions from a community of 459,976 IT Pros & Developers. It's quick & easy.

# new itertools functions in Python 2.6

4 Replies

 P: n/a On Jul 14, 1:26*pm, Mensanator

 P: n/a On Jul 15, 1:44 am, Raymond Hettinger 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 Jul 16 '08 #3

 P: n/a On Jul 16, 7:20*am, Mensanator >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')) ... 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 Jul 16 '08 #4

 P: n/a On Jul 16, 5:05 am, Mark Dickinson 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')) > 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 Jul 19 '08 #5

### This discussion thread is closed

Replies have been disabled for this discussion.