Promote combinations_with_replacement() from a recipe to a regular itertool.
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 @@
.. 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 @@
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