So, I'm looking for a general solution to the following problem. Let's say n persons want to give gifts between them and they decide that the best way is to choose one person for each and give one big gift instead of several small ones. The thing is that some of these people are married or siblings to others in the group and they don't want to give gifts to them (they are going to give them a present anyway). So, the problem is to design an algorithm to generate random selections for gifts avoiding the set of restrictions. I don't seem to be able to get an algorithm that is guaranteed not to hang. Can you?
 | November 16, 2009, 3:57 pm |
A Christmass Math Problem
Comments
Voilà:
each person represents a node of a graph. Let N be the set of nodes and N+ its mirror (you just repeat the same nodes).
Construct a a set of directed links from each node i in N to each node j in N+. Each link will have a cost of infinity (or a very large number) in the following cases:
i=j or i and j have a restriction.
If there is no reason why you should choose one person more than another, then all the other links have a cost of 1.
Now you want to minimize the assigment cost. For that you have two choices: either use a specialized assignment problem or, if you don't care about efficiency, just solve a minimum cost flow problem where the demands are all 1.
Reply to this comment
each person represents a node of a graph. Let N be the set of nodes and N+ its mirror (you just repeat the same nodes).
Construct a a set of directed links from each node i in N to each node j in N+. Each link will have a cost of infinity (or a very large number) in the following cases:
i=j or i and j have a restriction.
If there is no reason why you should choose one person more than another, then all the other links have a cost of 1.
Now you want to minimize the assigment cost. For that you have two choices: either use a specialized assignment problem or, if you don't care about efficiency, just solve a minimum cost flow problem where the demands are all 1.
Reply to this comment
Posted by
on November 25, 2009, 4:26 pm
on November 25, 2009, 4:26 pm
I propose this:
Assign a color to each group (brothers or partners)
Put each person's name in an envelope
Mark it on the outside with his/her color/s
Take turns
Select a random person from the largest remaining group (avoid deadlock)
Put all envelopes from other groups in a bag (no gift to brothers or partner)
The person secretly takes an envelope
Remove that person from his/her group/s
This avoids dead-lock and backtrack
But it requires an impartial party to fill the bag on each turn
Reply to this comment
Assign a color to each group (brothers or partners)
Put each person's name in an envelope
Mark it on the outside with his/her color/s
Take turns
Select a random person from the largest remaining group (avoid deadlock)
Put all envelopes from other groups in a bag (no gift to brothers or partner)
The person secretly takes an envelope
Remove that person from his/her group/s
This avoids dead-lock and backtrack
But it requires an impartial party to fill the bag on each turn
Reply to this comment
Posted by
liz
on December 1, 2009, 4:32 pm
on December 1, 2009, 4:32 pm
Alfredo! este es el 'amigo secreto' mas complicado que he visto en mi vida entera!
Reply to this comment
Reply to this comment
Bruni, I don't see the randomness in your solution. Is the plan to find all minima and chose one at random?
Reply to this comment
Reply to this comment
on November 17, 2009, 2:48 pm
Un abrazote
Reply to this comment
on November 17, 2009, 3:55 pm
Un abrazo grande a ti.
Reply to this comment