Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I need some expert answers to help me determine the most efficient algorithm in this scenario.

Consider the following data structures:

type B { A parent; }

type A {
   set<B> children;
   integer minimumChildrenAllowed;
   integer maximumChildrenAllowed;
}

I have a situation where I need to fetch all the orphan children (there could be hundreds of thousands of these) and assign them RANDOMLY to A type parents based on the following rules.

  1. At the end of the job, there should be no orphans left
  2. At the end of the job, no object A should have less children than its predesignated minimum.
  3. At the end of the job, no object A should have more children than its predesignated maximum.
  4. If we run out of A objects then we should create a new A with default values for minimum and maximum and assign remaining orphans to these objects.
  5. The distribution of children should be as evenly distributed as possible.
  6. There may already be some children assigned to A before the job starts.

I was toying with how to do this but I am afraid that I would just end up looping across the parents sorted from smallest to largest, and then grab an orphan for each parent.

I was wondering if there is a more efficient way to handle this?

EDIT:

  • Expanding upon the criteria for even distribution of children, we should attempt to avoid a situation where any one A has 2 or more children than any other A unless they started that way. For example, if A1 has 4 children, and A2 and A3 have 1 child each and there are 2 orphans, then A2 and A3 should each be assigned an orphan making an even distribution of 4, 3, and 3 children for each A.

  • Yes I understand we could end up where there is one orphan left and an A that has not met its minimum. This exception case will be handled by a separate algorithm that will try to evenly split an A into two objects and assign the remaining orphans amongst them.

EDIT: 2

Ok, I misunderstood the requirements in my situation. The data model for A shows minimum and maximum property but in fact this should be a global setting for every A. In essence it is a missed requirement that requires the data model to be refactored later.

All A will have the same minimum and maximum now. This actually changes things significantly! Sorry for the confusion.

share|improve this question
    
There is not always a solution to this problem, for example with n parents with 1 minimumChildrenAllowed and n-1 children. On a sidenote, what is the problem with doing it 1 by 1? This is the intuitive way to distribute the children evenly. A little optimization would be to find the minimum of "abs(p.children.length - p.minimumChildrenAllowed)", let's call it m. You then can distribute m children to every parent first. –  mcwise Sep 12 '12 at 20:17
    
If you have a fixed set of parents then does the children max make sense so much as an even balancing of children? Or are you going to create new parents when you've maxed the children counts for all the parents you have? Are you going to allocate to all the parents you have, and then the leftover orphans just go back to the orphanage? –  Jimmy Hoffa Sep 12 '12 at 21:09
    
Can you expand on your criteria for for how evenly distributed children should be? For example, if you were to score the algorithm's success, would the formula be the sum of squared deviations from the mean number of children (where 0 is a perfect score)? –  psr Sep 12 '12 at 21:29
    
@mcwise - Basically, yes, but some for some parents m will take them above their max, so you would just distribute up to their max. So it might take a few passes. –  psr Sep 12 '12 at 21:39
2  
@maple_shaft - According to your criteria you can't ensure that no A has 2 more children than any other. What if one A has min 1 max 2 and another has min 10 max 20? –  psr Sep 12 '12 at 23:23

2 Answers 2

up vote 5 down vote accepted
+150

I would:

  1. Calculate max*countOfA and min*CountOfA

  2. If you don't have enough B to fill all the minimum A values you can't actually meet the criteria you have listed.

  3. If you don't have enough A then add the minimum number you need (ceiling of (SumOfAMaxes-B)/DefaultMaximum). Update the sum of min and max values accordingly.

  4. You can now calculate the mean number of children for your set A. This is your target value. However, this will usually be fractional. Figure out how many items should be rounded down, and how many up. (Example, you have 100 parents and the mean is 3.4. 40 will have 3 as the target, and 60 will have 4 as the target).

  5. Loop through the parents and set them to the higher target value unless they are already that value or higher. Keep track of how many children you have left to allocate as you go. When you run out of the high value (in the above example you would have only 60 of them), assign the lower value.

  6. When you are done with 4 you may have some unassigned children because of existing parents that had more children than your target value. If so go back to step 4 but make sure your new target value is at least equal to the floor of the prior target value + 1.

This probably isn't optimal but it's pretty easy and probably not that far off optimal. It is quite similar to the original comment by mcwise, though a little improved and elaborated. Given the updated requirements there isn't that much to the problem.

share|improve this answer
    
Can you clarify on step 3? I am not sure I completely understand this step. –  maple_shaft Sep 13 '12 at 10:59
    
I'm just saying at the beginning you know at least the minimum number of extra parents you will need. (I actually forgot that you will have to loop back to step 3, rather than 4, because you may discover there was less room than you thought due to child records already existing). –  psr Sep 13 '12 at 16:40

Assuming you have existing A's with various numbers of B's already assigned to them, my first pass at this would probably be:

Sort the A's first on their number of B's (will call that the ChildCount), and then on a random number as the second sort factor. So you have a list of A's grouped by their ChildCount, lowest first, but then those with the same child count are randomly placed on the list amongst themselves. Then just start from the top, assigning B's one at a time to those A's with a ChildCount of 0. When thats done, start back at the top and do it for those with a ChildCount of 1. Then 2, etc. If an A reaches its max number of children, remove it from the list altogether. If you have a few B's left over, create the new A's and fill them up one at a time. To avoid 'orphans', if you mark the newly assigned B's as being new, you can take a few of those back from other A's with a max count, and balance things out (assuming this would be ok to do during 'assign time', and before everything is committed).

share|improve this answer
    
After thinking on this, this is close to my approach. I was wondering however if it would be more efficient to random sort the orphans instead of each list of A with common child count. Any thoughts? –  maple_shaft Sep 13 '12 at 11:02
1  
The main reason I suggest sorting the list of A's is so that the same ones dont always get the new B's first. So if on an average night you have enough new B's to fill half A's to 4, and the others to 3, its not the same A's each night getting filled to 4. I dont know if thats an issue or not (for ex, distributing sales leads, you dont want the same sales people to always get more leads). If its not, you can probably forgo the randomizing all together. –  GrandmasterB Sep 13 '12 at 18:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.