[issue17930] Search not needed in combinations_with_replacement

[Tim Peters]

Tim Peters added the comment:

There's another savings to be had when an index becomes the maximum:  in that case, all the indices to its right are already at the maximum, so no need to overwrite them.  This isn't as big a savings as skipping the search, but still buys about 10% more in the Python code.  Like so:

    def cwr3(iterable, r):
        pool = tuple(iterable)
        n = len(pool)
        if n == 0 and r:
            return
        indices = [0] * r
        yield tuple(pool[i] for i in indices)
        rmax, nmax = r-1, n-1
        j = rmax if n > 1 else -1
        while j >= 0:
            newval = indices[j] + 1
            if newval < nmax:
                indices[j:] = [newval] * (r - j)
                j = rmax
            else:
                assert newval == nmax
                indices[j] = newval
                j -= 1
            yield tuple(pool[i] for i in indices)

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue17930>
_______________________________________