Generate all multisets of length k for n symbols

Question

I am trying to generate a list of all multisets of length $k$ in a set with $n$ symbols. For example, if I had the set

$S = {A, B, C}$

I would expect the following output for $k = 2$ and $n = 3$:

$O = {(A,A),(A,B),(A,C),(B,B),(B,C),(C,C)}$

What is the proper way to go about generating this list?

Answer 1

I presume you want to do this algorithmically. In Mathematica:

Union[Sort /@ Tuples[{A, B, C}, 2]]

{{A, A}, {A, B}, {A, C}, {B, B}, {B, C}, {C, C}}

More generally:

myMultiSet[n_Integer, k_Integer] := Union[Sort /@ Tuples[Range[n], k]]

So for instance myMultiSet[5,3] yields

{{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 1, 4}, {1, 1, 5}, {1, 2, 2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 3}, {1, 3, 4}, {1, 3, 5}, {1, 4, 4}, {1, 4, 5}, {1, 5, 5}, {2, 2, 2}, {2, 2, 3}, {2, 2, 4}, {2, 2, 5}, {2, 3, 3}, {2, 3, 4}, {2, 3, 5}, {2, 4, 4}, {2, 4, 5}, {2, 5, 5}, {3, 3, 3}, {3, 3, 4}, {3, 3, 5}, {3, 4, 4}, {3, 4, 5}, {3, 5, 5}, {4, 4, 4}, {4, 4, 5}, {4, 5, 5}, {5, 5, 5}}

Answer 2

For large $n$ and $k$, the right thing to do is to create an iterator, which computes the next multiset given the current multiset. This is easy to do: find the rightmost entry less than $n$, increment it, and copy the result into every spot to the right:

NextMultiSet[s_, n_] := Block[{i, k = Length[s]},
   For[i = k, i > 0 && s[[i]] == n, i--];
   If[i == 0, Return[s]];
   Take[s, i - 1] ~Join~ Array[s[[i]] + 1 &, k - i + 1]];

By repeatedly calling NextMultiSet, starting with $\{1,1,\ldots,1\}$, you generate each of the $\binom{n+k-1}{k}$ multisets exactly once, in sorted order. This is feasible even if you don't have room to store (and thus sort) the entire list:

Timing[With[{n=20,k=8},
       Nest[NextMultiSet[#, n] &, Array[1 &, k],
       Binomial[n+k-1,k] - 1]]][[1]]
  43.765625

In contrast, myMultiSet won't run (on my cheap laptop) with these parameters:

myMultiSet[n_Integer, k_Integer] := Union[Sort /@ Tuples[Range[n], k]]
Timing[myMultiSet[20, 8]][[1]]
  General::nomem: The current computation was aborted because there was
  insufficient memory available to complete the computation.