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 <rep...@bugs.python.org> <http://bugs.python.org/issue17930> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com