I have a dataset in php with 7 elements, for simplicity we can assume it's the following:
$S = array("A", "B", "C", "D", "E", "F", "G");
I am trying to generate a list of all multisets in S for a variable (specifiable) number of elements per multiset.
For example, if I wanted all multisets with 2 elements, it would output the following (omitting quotes for simplicity):
{(A,A),(A,B),(A,C),(A,D),(A,E),(A,F),(A,G),(B,B),(B,C),(B,D),
(B,E),(B,F),(B,G),(C,C),(C,D),(C,E),(C,F),(C,G),(D,D),(D,E),
(D,F),(D,G),(E,E),(E,F),(E,G),(F,F),(F,G),(G,G)}
I know the multichoose formula to find the number of multisets [a,b] = [n-1,k] for (a+b)!/(a!b!), but dont know how to generate the actual multisets themselves.
To enumerate n multichoose k, enumerate n+k-1 choose k and then decrease position i of the result by i (indexing from 0).
For example, to enumerate 3 multichoose 3, enumerate 5 choose 3 and map
012 -> 000
013 -> 001
014 -> 002
023 -> 011
024 -> 012
034 -> 022
123 -> 111
124 -> 112
134 -> 122
234 -> 222.