Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
2  
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]. –  Artes May 15 '13 at 20:41
1  
@Artes: Tuples[] looks promising. Subsets[] is no good, as it doesn't produce repetitions -- try Subsets[{1,2},3] –  jnthn May 15 '13 at 20:51
    
Releated link,mathematica.stackexchange.com/questions/19141/… –  chyaong Sep 13 '13 at 16:16
    
Actually you are looking for the variations with repetition, for which the length of the result is always n^k. –  István Zachar Sep 14 '13 at 8:57

2 Answers 2

up vote 8 down vote accepted

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}} *)
share|improve this answer
    
Thanks! Your last sentence isn't yet clear to me, so I'll have to play with your code. –  jnthn May 16 '13 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.) –  Daniel Lichtblau May 16 '13 at 14:48
    
It's always nice to see an IntegerDigits solution! –  István Zachar Sep 14 '13 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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