Notices
Results 1 to 6 of 6

Thread: 'partitioning' problem?

  1. #1 'partitioning' problem? 
    Forum Freshman
    Join Date
    May 2009
    Posts
    33
    Hi everybody,
    I'm sure this problem has long been solved, but as I don't know what it's called (I'm not a mathematician) I wonder if anyone can help.

    Say you have a collection of N objects, each having a certain mass. You're given a box with M<N compartments, and you're asked to put all the objects in the box, partitioning them in such a way that the M compartments are as 'equilibrated' as possible, i.e. the mass is distributed as evenly as possible across the M compartments.

    Is there a known algorithm that does that? If not, how would you go about creating one?


    Reply With Quote  
     

  2.  
     

  3. #2 Re: 'partitioning' problem? 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by lavoisier
    Hi everybody,
    I'm sure this problem has long been solved, but as I don't know what it's called (I'm not a mathematician) I wonder if anyone can help.

    Say you have a collection of N objects, each having a certain mass. You're given a box with M<N compartments, and you're asked to put all the objects in the box, partitioning them in such a way that the M compartments are as 'equilibrated' as possible, i.e. the mass is distributed as evenly as possible across the M compartments.

    Is there a known algorithm that does that? If not, how would you go about creating one?
    I don't know of any canned algorithm of this type off the top of my head. Combinatorial questions of this type can be deceptively difficult.

    However, before any solution can be attempted you need to very clearly define what you mean by "equilibrated as possible". I can think of several possibilities.

    1. You might take as a measure of "equilibration" the sum of the absolute values of the difference between the mass in each compartment and the mean value.

    2. You might take as a measure of "equilibration" the square root of the sum of the squares of the difference between the mass in each box and the mean.

    3. You can even take as the measure of "equilibration" the [tex]p^{th}/tex] root of the sum of the absolute value of the differences between the mass and the mean to the power for .

    4. You can take as the measure of "equilibration" the maximum of the absolute values of the differences between the mass in each box and the mean.

    There are probably other ways to do this, but the ones I listed are the most common, and I would imagine either 1 or 4 is in line with your application, although 4 might be of interest if there is a step funtion in the condsequences of a large overdose or underdose.

    What is the real problem that prompts this question ? Quite often one can simplify the mathematics by translating the physical question to mathematics more simply.


    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    May 2009
    Posts
    33
    Hi DrRocket,
    I think I'd go for either 1 or 2.

    In principle, one could virtually build all possible distributions of the N objects in the M compartments, compute the 'variance' of each, and select the one(s) with the lowest variance (in fact, writing this made me realise that there is not necessarily a single solution... a bit like a bad Sudoku).
    However, I bet even for low N's this would be very time-consuming and probably computationally inefficient. I can't even think of a formula to count all possible distributions.

    In fact, a few years ago I tried to write an algorithm to solve this problem, based on a physical analogy.
    I imagined that the objects were like particles of liquid in M communicating vessels, and they could move from one to another in such a way that the level would get as even as possible.

    The algorithm analysed all possible pairs of compartments, and for each object i in compartment 1, it checked whether moving i to compartment 2 would result in a reduction of the variance. Then same again, but checking the effect of swapping object i in compartment 1 with object j in compartment 2. And so on until no further reduction was possible, through the usual sequence of loops you use in algorithms.
    I was not happy with the result; I wasn't sure this was the most efficient way to do it, and I wasn't sure the output was indeed the best distribution. Did I need to allow other types of operations between compartments? Etc.

    That's why I was asking for input.
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    This reminds me a bit of Huffman coding although I don't really know how applicable that is.
    Reply With Quote  
     

  6. #5  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by lavoisier
    Hi DrRocket,
    I think I'd go for either 1 or 2.

    In principle, one could virtually build all possible distributions of the N objects in the M compartments, compute the 'variance' of each, and select the one(s) with the lowest variance (in fact, writing this made me realise that there is not necessarily a single solution... a bit like a bad Sudoku).
    However, I bet even for low N's this would be very time-consuming and probably computationally inefficient. I can't even think of a formula to count all possible distributions.

    In fact, a few years ago I tried to write an algorithm to solve this problem, based on a physical analogy.
    I imagined that the objects were like particles of liquid in M communicating vessels, and they could move from one to another in such a way that the level would get as even as possible.

    The algorithm analysed all possible pairs of compartments, and for each object i in compartment 1, it checked whether moving i to compartment 2 would result in a reduction of the variance. Then same again, but checking the effect of swapping object i in compartment 1 with object j in compartment 2. And so on until no further reduction was possible, through the usual sequence of loops you use in algorithms.
    I was not happy with the result; I wasn't sure this was the most efficient way to do it, and I wasn't sure the output was indeed the best distribution. Did I need to allow other types of operations between compartments? Etc.

    That's why I was asking for input.
    This is not an algorithm that is guaranteed to get you to a minimum. But it is a procedure that ought to get you an acceptable distribution.

    1)Pick your measure of equilibrium from the list.

    2)Calculate the mean as the total weight divided by the number of compartments available.

    3)Make some inititial distribution of the lumps. It doesn't really matter what the distribution is, but a reasonably even distribution will be more computationally efficient than an uneven one.

    4)Find the cell with the largest postivie difference from the mean and the cell with the negative deviation largest in absolute value from the mean. Move the lumps from positive box to the negative box, using the smallest available lumps, until moving any additional lump would give the negative box a positive difference from the mean.

    5) Recalculate the measure for the ensemble and repeat from 4) until the algorithm stops or you get "close enough".

    I don't know a true algorithm that would result in an absolute minimum short of looking at all possibilities. Howeve, that number will be HUGE and I doubt any of us would live long enough to permit even a fast computer from evaluating all possibilities. Factorials get really big really fast.
    Reply With Quote  
     

  7. #6  
    Forum Freshman
    Join Date
    May 2009
    Posts
    33
    Thanks DrRocket, I see your approach is much more rational than mine.
    I'll give it a try when I have time.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •