Algorithm for Assigning Positions and Sorting People
Posted on 2013-06-04
I have an algorithm I am trying to write.
Here is a way to explain it using an analogy that is totally not relevant, but gets the point across.
Pretend I have two buckets. I am going to accept three people in each. I will be randomly picking from two separate groups. So, all the people in group A will only have a chance of being accepted into bucket A, and the people in group B will only have a chance of being accepted into bucket B.
However, I want the condition that if the individuals are married, a rare occurrence for the sake of this example, the individual automatically gets put in the bucket.
So, it could be that I put three random people from subset A into the bucket, and three random people from subset B into their bucket. The three people in subset A are not married to the three people from subset B, so this is the final situation and no changes are needed.
Say I put the three people in each bucket. It turns out that someone in bucket A was married to someone not put in bucket B. So, I kick the last person to be put in bucket B out, and put the spouse into bucket B. This solves the problem and no further changes are made.
Lastly, say I put three people in each bucket. It turns out that one person in each is married. So, I start by evaluating the last person into bucket A, who was married, and put their spouse into bucket B. I then evaluate bucket B. It turns out that one of the other individuals in bucket B was also married, so I put their spouse into bucket A. The spouses always get preference. But, in so doing, the last person who entered the bucket is kicked out, in this case, it was the individual who was married and, as a result, had their spouse put into bucket B when evaluated. By being kicked out, their spouse is now kicked out. While bucket B is now full with two regular people, and the spouse of the individual in bucket B, there is now a void in bucket B. So, another person is randomly picked to be put in bucket B. It turns out, though, that this randomly selected individual has a spouse who is married, so again their is a need to kick the last person, who was not a spouse, out of bucket A.
The issue is that each action, when evaluated, has a ripple effect. This was obviously an attempt to simplify a very complex problem. A more proper analogy might involve dozens of buckets in my case, each which can hold fifty people. So, there would be constant change, as every time a bucket is iterated other buckets change as a result; and when those buckets change, the source bucket may be impacted, leading to a condition which causes it to change other buckets.
Maybe it would be more helpful to explain the actual real-life scenario. That was the easiest idea I could come up with as an analogy. Is there some sort of algorithm that would handle this well? I don't really know where to start in designing this. It almost sounds like a recursive algorithm might be needed, as you are constantly re-evaluating something.
In every case a harmony has to be reached at some point. The situation is such that, while dozens of changes may be needed in a bucket before it is finally settled, when completed, all will be settled.
The other approach I thought of was simply tracking a boolean variable for each bucket indicating whether a change had occurred. I would have a while loop that would run through each bucket, essentially checking if any changes needed to be made to other buckets. The while loop would break when all of the boolean variables came back false, indicating that no changes were made as a result of that bucket. When no bucket, starting at the first and going to the last, has any more change to inflict on other buckets, it means we have reached that harmonious place. If even one bucket makes a change on another, its boolean value is set as true, and we again have to re-evaluate all buckets to make sure that there aren't additional changes needed stemming from the ripple effect made.
I am looking to incorporate this into Visual Basic code. I'd be happy to use Excel or something else to model it first, just to better understand what is going on.