Talk:Combinations with repetitions: Difference between revisions

Line 31:

:::: [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)

==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)