summaryrefslogtreecommitdiffstats
path: root/Doc/library
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2009-01-27 04:20:44 (GMT)
committerRaymond Hettinger <python@rcn.com>2009-01-27 04:20:44 (GMT)
commitd07d939c5ee312905cce50bf885e62d60e4e4a33 (patch)
tree84a847adc4d386082180c400c0ebc859a55b0809 /Doc/library
parentdd1b33a2edcbc46155cb6809809541f5d9f1b428 (diff)
downloadcpython-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.rst3
-rw-r--r--Doc/library/itertools.rst63
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