diff options
Diffstat (limited to 'Doc')
| -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 b358e38..5b25b47 100644 --- a/Doc/library/collections.rst +++ b/Doc/library/collections.rst @@ -291,8 +291,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 b7cd431..9aff478 100644 --- a/Doc/library/itertools.rst +++ b/Doc/library/itertools.rst @@ -139,6 +139,53 @@ loops that truncate the stream. .. versionadded:: 2.6 +.. 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 @@ -691,22 +738,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 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) - def unique_everseen(iterable, key=None): "List unique elements, preserving order. Remember all elements ever seen." # unique_everseen('AAAABBBCCDAABBB') --> A B C D |