2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 {... }} $\endgroup$
    – Marcelo Fornet
    Commented Dec 4, 2019 at 18:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Marcelo Fornet
    Commented Dec 4, 2019 at 18:50

1 Answer 1

Reset to default
2
$\begingroup$

Every such arrangement of 15 balls to 21 boxes corresponds, in a one-to-one fashion, to a string of the form *|**||||...|*, where there are a total of 35 symbols in the string, exactly 15 stars and 20 bars. (Think of each * as a ball, and each | as a divider between two boxes.) These, in turn, correspond to the set of binary strings of length 35 that contain exactly 20 one's, which in turn corresponds to the set of ways to choose a subset of 20 positions out of a set of 35 possibilities.

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think enumerating subset of size 20 of the set of size 35 is the question of OP. $\endgroup$
    – Marcelo Fornet
    Commented Dec 4, 2019 at 18:46
  • $\begingroup$ That is an interesting modelling that i didn’t know, thank you! And it has an obvious implementation. $\endgroup$
    – Christian H. Kuhn
    Commented Dec 4, 2019 at 19:10
  • $\begingroup$ @MarceloFornet, oh, ok! You could be right about that -- I may have misunderstood which part the poster was having difficulty with. I've edited my answer to provide more information on how to do that part of the task. $\endgroup$
    – D.W. ♦
    Commented Dec 4, 2019 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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