Partition algorithm to split set of objects

Question

Can somebody confirm if an algorithm exist to solve this? I assume even if something exist, it will be NP complete.

Lets say there is a Set<Set<Object>> where the total number of elements is 165. This has to be partitioned into three sets of each 55 elements(or lesser), such that elements in the inner set is not distributed among multiple sets after partition.

Please don't ditch this question as homework types. I have searched enough and I couldn't classify this algorithm properly for me to research efficiently.

such that elements in the inner set is not distributed among multiple sets after partition - this part is not clear,you mean each set needs to have a unique element...? — NoobEditor
– NoobEditor, Commented Sep 1, 2014 at 6:57
The input is a set of set of objects. The expected output is three different set of objects in such a way that all objects in inner set(in the input) go into the same set(one of the three output sets) and also the number of objects in each set doesn't exceed 55 (or any input input) — user378101
– user378101, Commented Sep 1, 2014 at 7:00

btilly · Accepted Answer · 2014-09-01 07:30:21Z

2

Yes, this exists and it is NP-hard. It is the bin-packing problem with the size of the bins being 55 and the size of the objects being the sizes of the inner sets.

See http://en.wikipedia.org/wiki/Bin_packing_problem for more.

answered Sep 1, 2014 at 7:30

btilly

47.8k3 gold badges69 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Kyle Strand Over a year ago

If I understand the problem correctly, this is not equivalent to the bin-packing problem, and in fact can be solved in polynomial time.

Collectives™ on Stack Overflow

Partition algorithm to split set of objects

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related