In terms of the twentyfold way, this is a multicombination (or n
-multisubset): You have 100 unlabeled balls (ingredients) that you want to distribute into N
labeled buckets (recipes) with no restriction on the counts. For 6 recipes, there about 108 multicombinations, but there are over 1012 ways to "brute force" the problem, so I suggest the recursive approach even for online challenges like these. Possibly they won't give you so many recipes it's a concern, though.
Or depending on the challenge, they may give you so many that you need to thin the search space in other ways even when you don't generate invalid states, e.g. having to discard large swaths of possible vectors due to the constraints around negative numbers so that you avoid billions of visits you would otherwise check.
I feel the recursive approach is rather understandable, and it's also pretty amenable to culling the problem space when necessary, since you can just not let a given index exceed a problematic cap, say. If I were doing the challenge, I'd probably just use that.
That's all the practical input I have.
However, just for fun, this seemed like a good chance to try implementing a more optimized algorithm in Rust. I remembered reading about a pseduo-Gray code for n-choose-k
combinations, where a bit string representing "chosen or not" changes minimally between each visit. (As discussed in the multicombination link, a multicombination can be modeled as a n-choose-k
combination.) "Pseudo" as at least two bits much change per visit in order to maintain the set bit count. It seemed like a nice fit since Rust supports 128-bit integers, and 28 recipes would result in too many multicombinations to visit them all, so the limitations are reasonable.
I chose Algorithm C for Chase's sequence from TAOCP . It uses bookkeeping instead of recursion; the generated sequence has enough structure that some sort of culling would be possible, but I didn't explore that at all. The algorithm is pretty much just directly translated from the book. Upon each visit, 1 ingredient moves from one recipe to another (one count goes down by 1 and another goes up by 1).
Again, I still recommend the recursive approach; it's pretty intuitive to wrap your head around and to understand the sequence order too, and how to jump around in it if needed. But I had fun and thought I'd share.