5
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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]. $\endgroup$
    – Artes
    May 15, 2013 at 20:41
  • 1
    $\begingroup$ @Artes: Tuples[] looks promising. Subsets[] is no good, as it doesn't produce repetitions -- try Subsets[{1,2},3] $\endgroup$
    – jnthn
    May 15, 2013 at 20:51
  • $\begingroup$ Actually you are looking for the variations with repetition, for which the length of the result is always n^k. $\endgroup$ Sep 14, 2013 at 8:57

2 Answers 2

10
$\begingroup$

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}} *)
$\endgroup$
3
  • $\begingroup$ Thanks! Your last sentence isn't yet clear to me, so I'll have to play with your code. $\endgroup$
    – jnthn
    May 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
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.