Talk:Combinations with repetitions: Difference between revisions
(→Task definition: How about this definition?) |
|||
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)
|
Revision as of 02:37, 19 November 2010
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)
Task definition
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]
- Combination of a repetitions list. list=(1, 2, 2, 3) k=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)
- The original implementation (now deleted for copyright reasons even though the example results were not copyrighted) had:
How about this definition?
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 = [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 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)