# 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!

Tietoa työnantajasta:
( 0 arvostelua ) Santa Clara, United States

Projektin tunnus: #30492929

## 7 freelanceria on tarjonnut keskimäärin \$159 tähän työhön

mbilal4

Hello there, I am expert C/C++ programmer having 6+ years of experience. I am ready to help you. Please contact me. Thank you Regards, Bilal

\$225 USD 2 päivässä
(47 arvostelua)
5.5
danilamakarov01

Hi I have just read your project in detail and I have rich experiences about your project. I can finish your project perfectly, on time. I am the best freelancer for the job. If you hire me, you can get good result fro Lisää

\$140 USD 3 päivässä
(61 arvostelua)
5.7
merinsinha

Senior C++ Expert. As 9+ years experiences in these field. I can give good quality work. I have read the guidelines of your work.I believe that i can provide you the best quality works you are anticipating from this pl Lisää

\$250 USD 4 päivässä
(9 arvostelua)
3.7
eulertoday

I have good experiences for C++/C coding and algorithms. I have read your all description carefully and I understand your requirement. So I think I can deliver you good result. Thanks

\$120 USD 2 päivässä
(4 arvostelua)
1.6
SerhiiK333

hi, I am interested in your project. if you want not to waste your time, please hire me. I work with high quality and deliver in time. please discuss detail via chat. Best Regards.

\$140 USD 7 päivässä
(1 arvostelu)
1.1
ant0504

Hi, I've read your description carefully. I have more than 11 years experience with C/C++/Algorithm. ************************************************************************************* I'm confident in your project w Lisää

\$100 USD 3 päivässä
(2 arvostelua)
1.1
IuriiSaakian

Dear Client! I'm really interested in your project and I can help you with my best. I'm good in coding such as C/C+,C#, JAVA and have good experiences in Data Structure and Algorithm. Lets discuss more detail in chat.

\$140 USD 1 päivässä
(0 arvostelua)
0.0