New submission from Tim Peters:
Each time thru, CWR searches for the rightmost position not containing the
maximum index. But this is wholly determined by what happened the last time
thru - search isn't really needed. Here's Python code:
def cwr2(iterable, r):
pool = tuple(iterable)
n = len(pool)
if not n and r:
return
indices = [0] * r
yield tuple(pool[i] for i in indices)
j = r-1 if n > 1 else -1
while j >= 0:
newval = indices[j] + 1
indices[j:] = [newval] * (r - j)
yield tuple(pool[i] for i in indices)
j = r-1 if newval < n-1 else j-1
There `j` is the rightmost position not containing the maximum index. A little
thought suffices to see that the next j is either r-1 (if newval is not the
maximum index) or j-1 (if newval is the maximum index: since the indices
vector is non-decreasing, if indices[j] was r-2 then indices[j-1] is also at
most r-2).
I don't much care if this goes in, but Raymond should find it amusing so
assigning it to him ;-)
----------
assignee: rhettinger
components: Extension Modules
keywords: easy
messages: 188686
nosy: rhettinger, tim_one
priority: low
severity: normal
stage: needs patch
status: open
title: Search not needed in combinations_with_replacement
type: performance
versions: Python 2.7, Python 3.5
_______________________________________
Python tracker <[email protected]>
<http://bugs.python.org/issue17930>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
