What is an efficient algorithm for randomly assigning a pool of objects to a parent using specific rules

Question

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.

Answer 1

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.

Answer 2

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).