jkeagle13
asked on
Algorithm for Assigning Positions and Sorting People
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.
Thanks,
Joseph Irvine
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.
Thanks,
Joseph Irvine
GwynforWeb
I think you are going to have to make your question more concise.
Suggest that you list your rules more concisely and without repeating any points.
One thing that I wasn't sure about in your rules. When you kick someone out, is that person put back into their respective group to possibly be picked randomly again, or are they discarded? In one case, you may have to consider whether an infinite loop occurs; in the other case, you may have to consider whether you will be left with an unfilled bucket(s).
One thing that I wasn't sure about in your rules. When you kick someone out, is that person put back into their respective group to possibly be picked randomly again, or are they discarded? In one case, you may have to consider whether an infinite loop occurs; in the other case, you may have to consider whether you will be left with an unfilled bucket(s).
Do you need to do the actual filling and kicking, or do you just need the end result?
Must the probabilities of each person ending up in a bucket be the same as you would get by following this exact procedure?
Do married pairs always belong to different buckets?
Must the probabilities of each person ending up in a bucket be the same as you would get by following this exact procedure?
Do married pairs always belong to different buckets?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
*and replace the one with lowest seniority number
depending how you number them, I meant to say Highest, but basically it's the last one in.
depending how you number them, I meant to say Highest, but basically it's the last one in.
If you need to prefill the buckets and evaluate them later then:
Fill A issuing seniority numbers
Fill B issuing seniority numbers
For each in A
if has spouse then remove number and replace the lowest seniority in B with spouse do not issue a number
Next
(Matched pairs in A and B now have no numbers)
For each numbered in B
if has spouse then replace the lowest seniority in A with spouse do not issue a number
Next
There is a preference towards couples, once a pair is identified they will not be removed. Is this correct?
Fill A issuing seniority numbers
Fill B issuing seniority numbers
For each in A
if has spouse then remove number and replace the lowest seniority in B with spouse do not issue a number
Next
(Matched pairs in A and B now have no numbers)
For each numbered in B
if has spouse then replace the lowest seniority in A with spouse do not issue a number
Next
There is a preference towards couples, once a pair is identified they will not be removed. Is this correct?
Once someone is picked, do they go back into the pool? Or to the end of the queue? Or out of the game entirely?
You could also alternate picking A's and B's, so there could only be an issue on the very last pick. If there is conflict, you can discard the couple and pick again or displace the last A. You can move the picked (but not selected) entity to first place in the next drawing.
You could also alternate picking A's and B's, so there could only be an issue on the very last pick. If there is conflict, you can discard the couple and pick again or displace the last A. You can move the picked (but not selected) entity to first place in the next drawing.
I see a conflict in the seniority of pairs. If a spouse is found for an A and added to the B bucket, does the B take on the seniority of the A, or does the A get demoted to the level of the newly added B ?
A ruling needs to be made for this and the rest should be quite straightforward.
In my examples above I have raised the newly added spouse to the seniority of the existing partner.
In the question these seem to vary, which is why you gained a void in one bucket by removing a couple after assuming that another couple take precedence "But, in so doing, the last person who entered the bucket is kicked out, in this case, it was the individual who was married". This is where adding A's spouse had precedence over B's existing spouse. The conflict needs to be resolved by the partnership taking equivalent seniority in their own bucket.
A ruling needs to be made for this and the rest should be quite straightforward.
In my examples above I have raised the newly added spouse to the seniority of the existing partner.
In the question these seem to vary, which is why you gained a void in one bucket by removing a couple after assuming that another couple take precedence "But, in so doing, the last person who entered the bucket is kicked out, in this case, it was the individual who was married". This is where adding A's spouse had precedence over B's existing spouse. The conflict needs to be resolved by the partnership taking equivalent seniority in their own bucket.
Can we assume that once a person has been put into a bucket (and one removed) for spousal reasons, that person can never be removed from the bucket?
ASKER
Hello,
To clarify on the rules, the lists to get into the buckets are randomly ordered to start with. So, there will be a list for A whose order is randomly determined, and a list for B whose order is randomly determined, of which the individuals are picked from the top to be added to the bucket.
If we then know that there are 20 spots in bucket A, and 30 spots in bucket B, we begin adding. Spouses always get preference over non-spouses when their spouse from the other list is in the bucket, and the preference is based on the order in which they appear in the list. So, if there were more spouses who should receive preference then there were positions, the order would be the order in which they appeared in the list from front to back. A spouse who should otherwise receive preference but appeared last on the list would not be included if the bucket were already filled; no room at that point.
So, we would start filling bucket A with the first 20 on the list, some of whom may be spouses of people in list A, some of whom may not. We don't care at this point, everyone is treated equally as no conditions have been met based on bucket B. We pull the spouses from list B to the bucket based on the spouses chosen in bucket A. We retain their spot. If their spouse in bucket A is kicked out as new spouses push the list down, the spouse returns to the point on the list they started from. We then start filling bucket B from the remainder of the spots needed.
This is where filling in the remainder may find a spouse from the list who then brings a new spouse in list A to the bucket, potentially kicking out a spouse from bucket A, and their corresponding spouse from bucket B.
So nobody is ever off the list; they just return to their pre-assigned random spot.
I think the logic should go something like this:
Pull the first 1-x until bucket A is full, where x is bucket capacity
Iterate through all items in bucket A
Has spouse? Y - place spouse in B
(A is now full)
Pull the first 1-x until bucket B is full, where x is bucket capacity - already filled spots
Iterate through all items in bucket B
Has spouse? Y - take spouse and insert into bucket A in relative order from list A
Bump last-in on bucket A back to original position on list A
Check if any changes were made to bucket A.
If no changes, bucket A and bucket B are both at stasis.
If changes, iterate through all items in bucket A and verify spouse is included in bucket B
If spouse not included in bucket B, add spouse and kick last-in to bucket.
Iterate through bucket B and verify all spouses are in bucket A.
If spouse not included in bucket A, add spouse and kick last-in to bucket.
Repeat until no changes are made in either bucket.
To clarify on the rules, the lists to get into the buckets are randomly ordered to start with. So, there will be a list for A whose order is randomly determined, and a list for B whose order is randomly determined, of which the individuals are picked from the top to be added to the bucket.
If we then know that there are 20 spots in bucket A, and 30 spots in bucket B, we begin adding. Spouses always get preference over non-spouses when their spouse from the other list is in the bucket, and the preference is based on the order in which they appear in the list. So, if there were more spouses who should receive preference then there were positions, the order would be the order in which they appeared in the list from front to back. A spouse who should otherwise receive preference but appeared last on the list would not be included if the bucket were already filled; no room at that point.
So, we would start filling bucket A with the first 20 on the list, some of whom may be spouses of people in list A, some of whom may not. We don't care at this point, everyone is treated equally as no conditions have been met based on bucket B. We pull the spouses from list B to the bucket based on the spouses chosen in bucket A. We retain their spot. If their spouse in bucket A is kicked out as new spouses push the list down, the spouse returns to the point on the list they started from. We then start filling bucket B from the remainder of the spots needed.
This is where filling in the remainder may find a spouse from the list who then brings a new spouse in list A to the bucket, potentially kicking out a spouse from bucket A, and their corresponding spouse from bucket B.
So nobody is ever off the list; they just return to their pre-assigned random spot.
I think the logic should go something like this:
Pull the first 1-x until bucket A is full, where x is bucket capacity
Iterate through all items in bucket A
Has spouse? Y - place spouse in B
(A is now full)
Pull the first 1-x until bucket B is full, where x is bucket capacity - already filled spots
Iterate through all items in bucket B
Has spouse? Y - take spouse and insert into bucket A in relative order from list A
Bump last-in on bucket A back to original position on list A
Check if any changes were made to bucket A.
If no changes, bucket A and bucket B are both at stasis.
If changes, iterate through all items in bucket A and verify spouse is included in bucket B
If spouse not included in bucket B, add spouse and kick last-in to bucket.
Iterate through bucket B and verify all spouses are in bucket A.
If spouse not included in bucket A, add spouse and kick last-in to bucket.
Repeat until no changes are made in either bucket.
Is it required to use the order given by the list?
What if we adjust the rank of each person with a spouse according to their spouses rank in order to get a consistent assignment that is equally as "fair" as the filling and kicking procedure?
If we are to consider the given order as "random" then any random order should be as good as any other random order, but if the order is determined for us and we must follow that exact order, then that's a different matter.
And if you have a specified procedure for using that ordered list, then it is not a question of developing an algorithm but a question of implementing a specified algorithm, in which case we would want to know in what programming language you would be implementing it in.
What if we adjust the rank of each person with a spouse according to their spouses rank in order to get a consistent assignment that is equally as "fair" as the filling and kicking procedure?
If we are to consider the given order as "random" then any random order should be as good as any other random order, but if the order is determined for us and we must follow that exact order, then that's a different matter.
And if you have a specified procedure for using that ordered list, then it is not a question of developing an algorithm but a question of implementing a specified algorithm, in which case we would want to know in what programming language you would be implementing it in.
If the buckets are different sizes, start by filling the largest. This will avoid putting someone in bucket B as they are a spouse of A and then removing the A for the same reason.
ASKER
Hello,
Lets take the following numbers
List A
10
13
14
12
11
List B
24
22
23
21
20
You can only accept two in each bucket. In this case, 12 and 22 are married, 13 and 23 are married, and 14 and 24 are married.
You start on List A and fill it with the first two on the list. The order does matter, even though it is random.
You have:
Bucket A
10
13
List A
14
12
11
You then go to evaluate bucket B. You check your logic first, see that 13 is in Bucket A, so you put 23 in bucket B first. You then grab the first off the list.
You have:
Bucket B
23 - spouse to 13
24 - first on list
List B
22
21
20
You then have to re-evaluate though, because 24 is now in Bucket B, 14 gets preference in Bucket A. 14 originally came after 10 on List A, so 14 goes into second spot, as they maintain their relative list positions for ordering. Doing so kicks 13 back to its original spot on the list.
You have:
Bucket A
10
14
List A
13
12
11
You have to then re-evaluate B. Because 13 is no longer on the list, 23 no longer gets priority.
Bucket B
24 - first on list
22 - second on list
List B
23
21
20
You then have to re-evaluate A. 22 is now in the bucket, so 12 gets preference. The preferences are given to their original relative list ordering.
Bucket A
14
12
List A
10
13
11
No further changes are needed to list B, and when evaluating list B, no further changes are needed to list A, so you are done.
It just so happens that 24 and 22 were first and second on list B. A slight re-ordering of the initial lists would have huge impact, though. The following assumes the first two spaces are in the bucket, and A is evaluated first.
A B
13 24 -> 13 23 -> 13 23
10 22 -> 10 24 -> 14 24
14 23 -> 14 22 -> 10 22
12 21 -> 12 21 -> 12 21
11 20 -> 11 20 -> 11 20
In that case it isn't the first two from list B that wind up in the bucket, positions one and two.
Also, this is a gross simplification. Each list has hundreds of spots, there are dozens of buckets, and it isn't a one-to-one relationship as represented with spouses. Some are one-to-none, some are one-to-one, and some are one-to-many, where the number of many may be across a variable number of buckets.
Is there any easier way than to constantly iterate back through each bucket until no changes are needed, then break out of the loop?
Thanks,
Joseph Irvine
Lets take the following numbers
List A
10
13
14
12
11
List B
24
22
23
21
20
You can only accept two in each bucket. In this case, 12 and 22 are married, 13 and 23 are married, and 14 and 24 are married.
You start on List A and fill it with the first two on the list. The order does matter, even though it is random.
You have:
Bucket A
10
13
List A
14
12
11
You then go to evaluate bucket B. You check your logic first, see that 13 is in Bucket A, so you put 23 in bucket B first. You then grab the first off the list.
You have:
Bucket B
23 - spouse to 13
24 - first on list
List B
22
21
20
You then have to re-evaluate though, because 24 is now in Bucket B, 14 gets preference in Bucket A. 14 originally came after 10 on List A, so 14 goes into second spot, as they maintain their relative list positions for ordering. Doing so kicks 13 back to its original spot on the list.
You have:
Bucket A
10
14
List A
13
12
11
You have to then re-evaluate B. Because 13 is no longer on the list, 23 no longer gets priority.
Bucket B
24 - first on list
22 - second on list
List B
23
21
20
You then have to re-evaluate A. 22 is now in the bucket, so 12 gets preference. The preferences are given to their original relative list ordering.
Bucket A
14
12
List A
10
13
11
No further changes are needed to list B, and when evaluating list B, no further changes are needed to list A, so you are done.
It just so happens that 24 and 22 were first and second on list B. A slight re-ordering of the initial lists would have huge impact, though. The following assumes the first two spaces are in the bucket, and A is evaluated first.
A B
13 24 -> 13 23 -> 13 23
10 22 -> 10 24 -> 14 24
14 23 -> 14 22 -> 10 22
12 21 -> 12 21 -> 12 21
11 20 -> 11 20 -> 11 20
In that case it isn't the first two from list B that wind up in the bucket, positions one and two.
Also, this is a gross simplification. Each list has hundreds of spots, there are dozens of buckets, and it isn't a one-to-one relationship as represented with spouses. Some are one-to-none, some are one-to-one, and some are one-to-many, where the number of many may be across a variable number of buckets.
Is there any easier way than to constantly iterate back through each bucket until no changes are needed, then break out of the loop?
Thanks,
Joseph Irvine
Is there any easier way than to constantly iterate back through each bucketWith pairs of spouses, I believe there are easier ways assuming we are allowed to re-order the lists, which I still haven't seen a clear answer on.
If family sets can have more than two people, then this has potential to become an instance of the Set Packing Problem, which does not have an easy solution, although there could still be easier ones than the filling and kicking procedure described.
ASKER
The lists cannot be re-ordered. Their absolute order is critical.
Spouses is the incorrect term, just used for an example that quickly fell apart. Each list item could have no relationship, a one-to-one relationship, or one-to-many relationship with items on other lists. All of those will be present in the list for each item.
Thanks!
Joseph
Spouses is the incorrect term, just used for an example that quickly fell apart. Each list item could have no relationship, a one-to-one relationship, or one-to-many relationship with items on other lists. All of those will be present in the list for each item.
Thanks!
Joseph
Using the two lists:
A)10,13,14,12,11 and B)24,22,23,21,20
You can load your buckets one item at a time and evaluate:
A gets 10
B gets 24, A gets spouse 14
Now A is full, B requires one more
B gets 22, there is a spouse 12 to add to A.
Here is your conflict.
A already holds 10 and 14 which are both higher than 12 so take precedence in bucket A
but you want to replace 14 with 12 because you just added 22 to B.
There is already a higher precedence, 24 is at the top of list B.
Perhaps bucket A's list order has a higher importance than list B's order?
There has to be a clear ruling, either the spouse connection is first, or the list order, it cannot be both.
A)10,13,14,12,11 and B)24,22,23,21,20
You can load your buckets one item at a time and evaluate:
A gets 10
B gets 24, A gets spouse 14
Now A is full, B requires one more
B gets 22, there is a spouse 12 to add to A.
Here is your conflict.
A already holds 10 and 14 which are both higher than 12 so take precedence in bucket A
but you want to replace 14 with 12 because you just added 22 to B.
There is already a higher precedence, 24 is at the top of list B.
Perhaps bucket A's list order has a higher importance than list B's order?
There has to be a clear ruling, either the spouse connection is first, or the list order, it cannot be both.
Looking purely at the two simple lists, I would have thought that A)13,14 B)24,23 would trump the A)14,12 B) 24,22 that you derived as the 13-23 pair look higher in the lists than the 12-22.
I'm still puzzled about the question we are trying to answer.
If so, it should be precisely specified, but if it is, what question is there left for us to answer?
If you care mainly about the result at the end of the procedure, then the criticality of the original absolute order seems strange, since all the intermediate steps can obscure the relationship between the original order and the final result.
Can you express what the requirements are on the end result in terms of the original list orders?
I would also observe that if the relationships can come in sets of threes, then determining whether the buckets can be filled at all can be an NP-Complete problem.
Their absolute order is criticalIs the exact filling and kicking procedure also a critical requirement?
If so, it should be precisely specified, but if it is, what question is there left for us to answer?
If you care mainly about the result at the end of the procedure, then the criticality of the original absolute order seems strange, since all the intermediate steps can obscure the relationship between the original order and the final result.
Can you express what the requirements are on the end result in terms of the original list orders?
I would also observe that if the relationships can come in sets of threes, then determining whether the buckets can be filled at all can be an NP-Complete problem.
Is there any easier way than to constantly iterate backWhat are we allowed to change in order to make it easier?
Decisions regarding which bucket to fill when, or when and where to scan for kicking candidates can affect the efficiency of the procedure, and also the relationship between the end result and the absolutely critical input order, so what relationships between the input order and the end result do we need to preserve?