# How to enumerate multisets?

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.

• Look at Tuples[{1, 2, 3, 4, 5, 6, 7, 8}, 3]. Another interesting tip might be Subsets[{1, 2, 3, 4, 5, 6, 7, 8}, 3]. May 15, 2013 at 20:41
• @Artes: Tuples[] looks promising. Subsets[] is no good, as it doesn't produce repetitions -- try Subsets[{1,2},3] May 15, 2013 at 20:51
• Actually you are looking for the variations with repetition, for which the length of the result is always n^k. Sep 14, 2013 at 8:57

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}} *)

• Thanks! Your last sentence isn't yet clear to me, so I'll have to play with your code. May 16, 2013 at 0:35
• 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.) May 16, 2013 at 14:48
• It's always nice to see an IntegerDigits solution! 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.