Given the eight-element set {1,2,3,4,5,6,7,8}, I would like to enumerate all multisets (subsets with repetition) of size n, where n >= 3. For example, with n = 3, the sets {1,1,1}, {1,1,2}, ..., {8,8,7}, {8,8,8} would all be found. Ideally, I would like to be able iterate through each set, rather than create one gigantic program-crashing list, so that I can use each set at the time it is found. Since Binomial[n, k] only works for values of k <= n, I'm not sure how to best go about this.
$\begingroup$
$\endgroup$
3
2 Answers
$\begingroup$
$\endgroup$
3
This will generate all of them, just like Tuples. Not too hard to redo so as to get one at a time. Just use the correspondence between k-digit numbers base n (n=length of input set) and subsets length k allowing repetitions.
takeWithRepitions[set_, k_] :=
Module[{n = Length[set], rule, vals},
rule = Thread[(Range[n] - 1) -> set];
vals = Map[IntegerDigits[#, n, k] &, Range[0, n^k - 1]];
Map[# /. rule &, vals]]
Example:
takeWithRepitions[Range[5], 2]
(* Out[376]= {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 2}, {2,
3}, {2, 4}, {2, 5}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {3, 5}, {4,
1}, {4, 2}, {4, 3}, {4, 4}, {4, 5}, {5, 1}, {5, 2}, {5, 3}, {5,
4}, {5, 5}} *)
answered May 15, 2013 at 22:24
-
$\begingroup$ Thanks! Your last sentence isn't yet clear to me, so I'll have to play with your code. $\endgroup$– jnthnMay 16, 2013 at 0:35
-
$\begingroup$ What I meant was that you can order these sets in a particular way. Say the full set has length n and your subsets have length k. You can order so that the rth one is given by the digits, base n, of r-1. Just remember to use leading zeros, and to have the correspondende 0-> first element, 1->second element, .... (If this is still not clear, I can add an edit to show explicitly.) $\endgroup$ May 16, 2013 at 14:48
-
$\begingroup$ It's always nice to see an
IntegerDigitssolution! $\endgroup$ Sep 14, 2013 at 8:38
$\begingroup$
$\endgroup$
The "Multisets" package by David Bevan will generate a list of them, (without the duplication that comes from using "Tuples" or the "takeWithRepitions" function described by Daniel Lichtbau). http://library.wolfram.com/infocenter/MathSource/8115/
However, it does not appear to allow the iteration you want.
Tuples[{1, 2, 3, 4, 5, 6, 7, 8}, 3]. Another interesting tip might beSubsets[{1, 2, 3, 4, 5, 6, 7, 8}, 3]. $\endgroup$n^k. $\endgroup$