# Algorithm for creating n-multiset out of x?

I have a problem that can be modelled by 15 undistinguishable balls to 21 boxes. The state of a node is defined by indices from 1 to 21 and corresponding values from 0 to 15, with the constraint that the sum of all values is 15. Those are the nodes of my (sparse) graph, the edges are defined by the rule: diminish the (non-null) value of an index by 1 and add 1 to (index +1). The values are the balls, the indices are the boxes.

Following the twelvefold way, i find that i have to create 15-multisets out of 21 and that there are $$\binom{n + x - 1}{k}$$ possibilities. In my case, those are 3.2E10 which is small compared to 21 to the 15th power (6.8E20) and can be kept in the memory of my machine.

What i now need is an algorithm for the creation of all nodes. The primitive way would be 15 nested loops counting from 1 to 21, inside of all doing some tests if the node is a permutation of (and so identical with) an already created node, but that would be too time-consuming (6E20 possibilities). Is there a faster way, looking only at the 3E10 "real" states?

• A really bad, but working idea is: instead of 15 loops from 1 to 21, you can do 15 loops so that each loop start at the next position of the previous loop, something like: for i = 1..21 { for j = i+1..21 {... }} – Marcelo Fornet Dec 4 '19 at 18:49
• But in practice I just recommend you take a look at the solution proposed by @D.W. There are already tools to do this on several languages, usually under library named like itertools. – Marcelo Fornet Dec 4 '19 at 18:50

It follows that you can enumerate the set of valid nodes by enumerating all ways to choose a subset of size 20 that's contained in $$\{1,2,\dots,35\}$$. There are standard ways to perform this enumeration. One way is to use the combinatorial number system, which creates a correspondence between these subsets and integers in the range $$\{1,2,\dots,{35 \choose 20}\}$$. See also https://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations, Get a fixed-size family of k-element subsets, https://cs.stackexchange.com/a/72543/755 for more.