Databases
StackOverflow2013
Postsdbo
POAlgorithm for best suiting people's choices from a definite list of items where there is only one of each available?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgorithm for best suiting people's choices from a definite list of items where there is only one of each available?
    primarykey
    data
    text
    <p>Ladies and Gents,</p> <p>My best friends and I do a "Secret Santa" type gift exchange every year, this year I've been trying to think of a couple of ways to make it interesting. There are six of us involved and I want to design a small program that allows the six of us to rank their preferred gift-recipients from 1 to 5 as well as their preferred gift-givers.</p> <p>So, let's say we're called A, B, C, D, E and F.</p> <p>A submits two lists:</p> <blockquote> <p>List 1 - People I would most like to give a present to: B, D, C, F, E</p> <p>List 2 - People I would most like to recieve a present from: F, D, E, B, C</p> </blockquote> <p>All six of us will submit both these lists, so I'll have 12 lists all together. I suppose my question is what is the best algorithm to now go ahead and assign each person a gift recipient?</p> <p>I thought of something like this:</p> <p>If two people have both selected each other in their opposing lists (i.e. A most wants to give to B, B most wants to get from A) then I immediately assign A to B. So now A is removed from our list of gift-recipients and B is removed from our pool of gift-givers.</p> <p>Once I've assigned the "perfect matches" I'm kind of lost though, is there an establish algorithm for situations like this? Obviously it's only for entertainment value but surely there must be a "real" application of something similar? Perhaps timetabling or something?</p> <p>My Google-fu has failed me but I have a feeling it might just be due my own lack of precision in search terms.</p> <p>Cheers, (and Happy Holidays I guess), Rob</p> <hr> <h2>Update / Part 2</h2> <p>Okay, <a href="https://stackoverflow.com/users/30202/ying-xiao">Ying Xiao</a> came to the rescue by recommending the <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem" rel="nofollow noreferrer">Gale Shapley Algorithm</a> for the <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem" rel="nofollow noreferrer">Stable Marriage Problem</a> and I've implemented that in Python and it works a treat. However, this is just a thought that occurred to me. I guess within our group of six best friends there are three pairings of "extra-best" friends so I have a feeling we'll just end up with three pairs of AB, CD, EF and BA, DC, FE in terms of gift giving and recieving.</p> <p>Is there an algorithm we could design that did take peoples rankings into account but also restricted two people forming a "closed group"? That is, if A is assigned to buy a gift for B, B <strong>can not</strong> be assigned to buy a gift for A? Perhaps I need to solve the <a href="http://en.wikipedia.org/wiki/Stable_roommates_problem" rel="nofollow noreferrer">Stable roommates problem</a>?</p> <p>Related questions:</p> <ul> <li><a href="https://stackoverflow.com/questions/273567/secret-santa-algorithm">Secret santa algorithm.</a></li> <li><a href="https://stackoverflow.com/questions/268682/what-is-the-best-low-tech-protocol-to-simulate-drawing-names-out-of-a-hat-and-e">What is the best low-tech protocol to simulate drawing names out of a hat and ensure secrecy?</a></li> </ul>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USRob Burke
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAlgorithm for best suiting people's choices from a definite list of items where there is only one of each available?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POAlgorithm for best suiting people's choices from a definite list of items where there is only one of each available?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POAlgorithm for best suiting people's choices from a definite list of items where there is only one of each available?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis is a lot of work for Secret Santa. I thought the point of Secret Santa was for it to be secret and random.(?) Pick names out of a hat! It's more fun that way.
      singulars
      1. POAlgorithm for best suiting people's choices from a definite list of items where there is only one of each available?
      1. USl15a
    2. COLisa, chances are we'll do exactly that. Although traditionally we've all put our phones into a bag and pulled them out, noted whose phone we got and then returned them. We've been doing it for years though so wanted some way to spice things up!
      singulars
      1. POAlgorithm for best suiting people's choices from a definite list of items where there is only one of each available?
      1. USRob Burke
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload