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.
2 Answers
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}} *)
-
$\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
IntegerDigits
solution! $\endgroup$ Sep 14, 2013 at 8:38
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$