CODEWITHSUNDEEP
algorithmpuzzlepartitioning
Sushant
Sushant

Reputation: 1074

Partition a sorted list subject to a constraint

Here is the question:

Given a sorted list of say Integers (you can assume they are positive, if its makes the problem any simpler), partition the list into 'n' equal size partitions (or as equal as possible), subject to the constraint that none of the integers appears more than one such partition.

The constraint essentially means that if you have a list {1,1,2,2}

then all the ones have to be in the same set, and all the 2's have to be in the same set. All 1's and all 2's can be in one set too. But we can't have one of the 1's in first partition and the second 1 in the second partition.

Example 1: 

    List: {1,1,2,2,3,3,4,4}


    Number of partitions to make: 4

    Answer: {1,1} {2,2} {3,3} {4,4}

Example 2: (trickier one) 

List: {1,1,2,2,2,3,3,4,4,4,4,4,4,4,4} 

Number of partitions to make : 3

Answer: {1,1,2,2} {3,3} {4,4,4,4,4,4,4,4}

    OR: {1,1} {2,2,3,3} {4,4,4,4,4,4,4,4}

Note here that the 3rd partition has to be of size 8, because due to the constraint all the 4's have to be in the same partition.

There can be numerous other tricky cases. Let me know if anyone needs more examples.

So the questions is what is the best way to approach or solve this problem?

Upvotes: 1

Views: 268

Answers (2)

genisage
genisage

Reputation: 1169

This is a sneaky version of the k-partition problem or the bin packing problem. If you count the number of occurrences of each element, and put those counts into a multiset, then you're basically trying to partition those numbers into sets that have the same sum.
If n=2, there are some pseudo-polynomial algorithms for it. Otherwise there's are no known pseudo-polynomial algorithms. (and can't be unless P=NP)
As for how to approach it. If you get to choose n, just set it to 1 and partition the list into itself. If you don't, but you have small lists, just implement a brute force solution. If you don't choose n, and you have long lists, look into greedy/approximation algorithms, and try to define exactly what you mean by "as equal as possible." (Do you mean the maximum difference? The variance? something else?)
Good luck.

Upvotes: 0

sethu
sethu

Reputation: 1721

The simplest solution I can think of is,

  1. First find all same elements in the list (Use something like hashing to find them or counting sort if you know the range before hand) and also maintain their size.

  2. Now you will have sets of repeating numbers (like {1,1} {2,2}) . After this step, try to find the number of lists you have and group them to form n number of partitions (as specified in the problem statement). For ex. In your last tricky example, we will have 4 lists in the end, u need 3 partitions. You can find 2 small lists and combine them to form 1, repeat this till you reach the required number of partitions.

Upvotes: 1

Related Questions