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$
  • 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 '13 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 '13 at 20:51
  • $\begingroup$ Releated link,mathematica.stackexchange.com/questions/19141/… $\endgroup$ – chyanog Sep 13 '13 at 16:16
  • $\begingroup$ Actually you are looking for the variations with repetition, for which the length of the result is always n^k. $\endgroup$ – István Zachar Sep 14 '13 at 8:57
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$
  • $\begingroup$ Thanks! Your last sentence isn't yet clear to me, so I'll have to play with your code. $\endgroup$ – jnthn May 16 '13 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$ – Daniel Lichtblau May 16 '13 at 14:48
  • $\begingroup$ It's always nice to see an IntegerDigits solution! $\endgroup$ – István Zachar Sep 14 '13 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, privacy policy and cookie policy

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