diff options
author | Raymond Hettinger <python@rcn.com> | 2009-01-27 04:20:44 (GMT) |
---|---|---|
committer | Raymond Hettinger <python@rcn.com> | 2009-01-27 04:20:44 (GMT) |
commit | d07d939c5ee312905cce50bf885e62d60e4e4a33 (patch) | |
tree | 84a847adc4d386082180c400c0ebc859a55b0809 /Doc/library | |
parent | dd1b33a2edcbc46155cb6809809541f5d9f1b428 (diff) | |
download | cpython-d07d939c5ee312905cce50bf885e62d60e4e4a33.zip cpython-d07d939c5ee312905cce50bf885e62d60e4e4a33.tar.gz cpython-d07d939c5ee312905cce50bf885e62d60e4e4a33.tar.bz2 |
Forward port r69001: itertools.combinations_with_replacement().
Diffstat (limited to 'Doc/library')
-rw-r--r-- | Doc/library/collections.rst | 3 | ||||
-rw-r--r-- | Doc/library/itertools.rst | 63 |
2 files changed, 48 insertions, 18 deletions
diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst index 169293f..0503ad29c 100644 --- a/Doc/library/collections.rst +++ b/Doc/library/collections.rst @@ -279,8 +279,7 @@ counts less than one:: Section 4.6.3, Exercise 19*\. * To enumerate all distinct multisets of a given size over a given set of - elements, see :func:`combinations_with_replacement` in the - :ref:`itertools-recipes` for itertools:: + elements, see :func:`itertools.combinations_with_replacement`. map(Counter, combinations_with_replacement('ABC', 2)) --> AA AB AC BB BC CC diff --git a/Doc/library/itertools.rst b/Doc/library/itertools.rst index d281278..aba1e25 100644 --- a/Doc/library/itertools.rst +++ b/Doc/library/itertools.rst @@ -133,6 +133,53 @@ loops that truncate the stream. The number of items returned is ``n! / r! / (n-r)!`` when ``0 <= r <= n`` or zero when ``r > n``. +.. function:: combinations_with_replacement(iterable, r) + + Return *r* length subsequences of elements from the input *iterable* + allowing individual elements to be repeated more than once. + + Combinations are emitted in lexicographic sort order. So, if the + input *iterable* is sorted, the combination tuples will be produced + in sorted order. + + Elements are treated as unique based on their position, not on their + value. So if the input elements are unique, the generated combinations + will also be unique. + + Equivalent to:: + + def combinations_with_replacement(iterable, r): + # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC + pool = tuple(iterable) + n = len(pool) + if not n and r: + return + 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:] = [indices[i] + 1] * (r - i) + yield tuple(pool[i] for i in indices) + + The code for :func:`combinations_with_replacement` can be also expressed as + a subsequence of :func:`product` after filtering entries where the elements + are not in sorted order (according to their position in the input pool):: + + def combinations_with_replacement(iterable, r): + pool = tuple(iterable) + n = len(pool) + for indices in product(range(n), repeat=r): + if sorted(indices) == list(indices): + yield tuple(pool[i] for i in indices) + + The number of items returned is ``(n+r-1)! / r! / (n-1)!`` when ``n > 0``. + + .. versionadded:: 2.7 + .. function:: compress(data, selectors) Make an iterator that filters elements from *data* returning only those that @@ -608,22 +655,6 @@ which incur interpreter overhead. s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) - def combinations_with_replacement(iterable, r): - "combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC" - # number items returned: (n+r-1)! / r! / (n-1)! - pool = tuple(iterable) - n = len(pool) - indices = [0] * r - yield tuple(pool[i] for i in indices) - while True: - for i in reversed(range(r)): - if indices[i] != n - 1: - break - else: - return - indices[i:] = [indices[i] + 1] * (r - i) - yield tuple(pool[i] for i in indices) - def unique_everseen(iterable, key=None): "List unique elements, preserving order. Remember all elements ever seen." # unique_everseen('AAAABBBCCDAABBB') --> A B C D |