Algorithm for constrained set partition (combinatorics with C++)

need a reasonably efficient algorithm implemented for a specific integer partition problem. In short, I have a multiset of integers, each of which belongs to a subset. I don't know the matching of integers to subsets; only the number and sum of elements in each subset. In general this means there are multiple partitions that fit the constraint. If we assume these partitions are equally likely, I want to find the likelihood that each integer value may belong to each of the subsets. I have written a more formal description of the problem here: [login to view URL] I've been struggling to find a good algorithm for this presumably NP-hard problem. It's clearly related to the set partition problem, but I'm having trouble finding the right approach given the many, many variants out there. Deliverables C++ code which takes two arbitrary tables of integers as input (see PDF for an example), and outputs a table with four columns: each integer value x_k from the multiset, repeated for each of the subsets in column 2 the subset id j=1,...,J, repeated as needed to produce each combination with column 1 the number of possible partitions where integer x_k is in subset j (numerator of the probability) the number of possible partitions (denominator of the probability) – same value for all rows I need an algorithm that does not need all partitions in memory as it enumerates through them, or it may fail on more complex cases. Some lexicographic approach would be ideal in case e.g. I want to parallelize the code later or sample partitions rather than fully enumerate (this is NOT part of this request!). The use of GMP might be a good idea to handle larger integers. We can decide on the data format that's most convenient for input and output. I think CSV may be okay at this stage. I'll provide some examples for testing the algorithm. This code will be used for academic research, and may be published at some point in the future, so I'd like to put the code under a MIT license (negotiable). Soft deadline, but the sooner the better of course :) Happy to clarify anything that's not entirely clear!