Talk:Combinations with repetitions: Difference between revisions
Content added Content deleted
(→Task definition: How about this definition?) |
|||
Line 31: | Line 31: | ||
:::: [1, 2] |
:::: [1, 2] |
||
::If it were "sampling with replacement" I imagine that that result would have also included [1,1] and [3,3]. Since it did not, I do not think we can have (a,a,a) as a result for set n= ('a,a,b,c,d'), k=3. But perhaps the results from the deleted example should be reposted as a part of the task description? --[[User:Rdm|Rdm]] 21:58, 18 November 2010 (UTC) |
::If it were "sampling with replacement" I imagine that that result would have also included [1,1] and [3,3]. Since it did not, I do not think we can have (a,a,a) as a result for set n= ('a,a,b,c,d'), k=3. But perhaps the results from the deleted example should be reposted as a part of the task description? --[[User:Rdm|Rdm]] 21:58, 18 November 2010 (UTC) |
||
==How about this definition?== |
|||
From the [http://docs.python.org/py3k/library/itertools.html#itertools.combinations_with_replacement Python documentation]: |
|||
'''itertools.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: |
|||
:<lang python>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 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)</lang> |
|||
:The code for combinations_with_replacement() can be also expressed as a subsequence of [http://docs.python.org/py3k/library/itertools.html#itertools.product product()] after filtering entries where the elements are not in sorted order (according to their position in the input pool): |
|||
:<lang python>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)</lang> |
|||
:The number of items returned is <code>(n+r-1)! / r! / (n-1)! when n > 0</code>. |
|||
We would need to '''change the page name''' to ''Combinations with replacement'', but I think the above Python does what the [[wp:Combination#Example of counting multicombinations|wp entry]] is trying to describe as: |
|||
:<lang python>>>> from itertools import combinations_with_replacement |
|||
>>> len(list(combinations_with_replacement('1234567890', 3))) |
|||
220</lang> |
|||
--[[User:Paddy3118|Paddy3118]] 02:37, 19 November 2010 (UTC) |