# Talk:Combinations with repetitions

Original implementations needed; the linked site does not indicate any license or copyright notice, which leads it to default (at least where Rosetta Code is based out of) to a default of "all rights reserved." The task can likely go to non-draft once it's slightly cleaned up, and original implementations are provided. --Michael Mol 19:39, 16 November 2010 (UTC)

Suggestion: It is OK. We can remove the Java solution. The other solutions are original implementation. Do I must remove it, or do you do it? Pelci 19:18, 18 November 2010 (UTC)

I pulled it myself. However, I don't mind if others want to pull them first, particularly in cases of clear copyright issues. --Michael Mol 19:20, 18 November 2010 (UTC)
So we can put back the task into the tasks... Pelci 19:40, 18 November 2010 (UTC)
I'd still want to see some cleanup of the task description. Mostly for en-us (or en-anything) grammar and spelling corrections. It might make more sense to wait until we have a few more implementations; as people attempt to implement it, they often find non-obvious problems we need to fix. --Michael Mol 19:43, 18 November 2010 (UTC)

At this stage, it's very hard for me to work out exactly what is to be implemented; the task gives very little guidance over what a “k-combination with repetition” is exactly (it's not the clearest of wikipedia pages that is linked to). At the very least, I'd expect it to use a simple small example (with as few elements as possible) to show exactly what is meant and how things differ from a standard combination-enumerator; it could then ask for the generation of the combinations for a larger input set. –Donal Fellows 23:31, 16 November 2010 (UTC)

Ditto on the lack of clarity.
What would be the result of:
```   n=(1,2,3), k=2;
n=(1,1,2,3), k=2
n=(1,1,1,2,3), k=2
```
And how do you compute the result in the general case? --Paddy3118 00:01, 17 November 2010 (UTC)
n=(1,2,3), k=1 would have the same result as n=(1,1,2,3), k=1. Similarly, (1,1,2,3), k=2 would be the same result as (1,1,1,2,3), k=2. One way of expressing the result would be: calculate all the possibilities and then eliminate the duplicate results. --Rdm 15:18, 17 November 2010 (UTC)

I wrote an example about the task! Pelci 19:44, 18 November 2010 (UTC)

The written example in the task description seems to describe sampling with replacement rather than sampling with repetitions. Which does the task attempt to describe? Given the set n= ('a,a,b,c,d'), k=3; (a,a,a) would be a valid answer if sampling with replacement, however would not be valid if sampling with repetition - which from the wikipedia page I understand to mean that some items may occur more than once in the population to be sampled.--Tikkanz 21:52, 18 November 2010 (UTC)
The original implementation (now deleted for copyright reasons even though the example results were not copyrighted) had:
Combination of a repetitions list. list=(1, 2, 2, 3) k=2
[2, 2]
[1, 3]
[2, 3]
[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? --Rdm 21:58, 18 November 2010 (UTC)

From the 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 =  * 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 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 `(n+r-1)! / r! / (n-1)! when n > 0`.

We would need to change the page name to Combinations with replacement, but I think the above Python does what the wp entry is trying to describe as:

<lang python>>>> from itertools import combinations_with_replacement

>>> len(list(combinations_with_replacement('1234567890', 3))) 220</lang>

--Paddy3118 02:37, 19 November 2010 (UTC)

Maybe keep the name as googlefight prefers it 465 to 91. --Paddy3118 02:45, 19 November 2010 (UTC)
I think we have two separate tasks here. We have the original task (where individual items could be repeated with counts independent of other items) and the new task (where the repetition count on all items is assumed to be at least as large as the number of elements in the desired results). --Rdm 15:58, 19 November 2010 (UTC)
And yet I get the n=10, k=3 result of 220 which is mentioned in the Wikipedia article?
Looking again at the previous description of:
Write a program which generates the all k-combination with repetitions of n different objects. (Practically numerals!)