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.


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!

Taidot: C++ -ohjelmointi, Matematiikka, Algoritmi

Näytä lisää: magento constraint fk_sales_order_customer foreign key customer_id references customer_entity entity_id delete set null update c, algorithm and data structure in c, algorithm for binary search in c, algorithm for prime numbers in c, algorithm for priority queue in c, algorithm of binary search in c, algorithm of prime number in c, disjoint set data structure c code, linked list algorithm in data structure using c, set bit in c, set bits in c, how to write algorithm for for loop in c, dijkstra algorithm using priority queue in c++, how to set timer in c#, disjoint set data structure c++, you don t know js 6 volumes set, algorithm for simple calculator in c, algorithm for snake game in c, don't know how to build task 'db:environment:set'

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


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)

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)

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)

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)

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)

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)

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)