I figure it's time to get onto this so that I'm ready for christmas already.

I have an group of people who must purchase presents for each other. However, they've been doing this for a couple of years and they don't want to get the same person again and again. So I have a data structure. A hash of lists where the hash keys are the people and the lists are the people they've bought for in the past: 

%people = (
    jim    => ['betty',  'claire'],
    betty  => ['frank',  'jim'   ],
    frank  => ['claire', 'john'  ],
    claire => ['john',   'betty' ],
    john   => ['jim',    'frank' ],
    nancy  => ['',       ''      ],             # new girl
);

[download]

This means that jim wont get betty or claire this year, betty wont get frank or jim and so on.

So last year I took this data structure and ran 'trial and error' computing on it. I started with jim, grabbed a list of the keys, removed jim, betty and claire, then picked a random result. No worries, lets say he gets nancy. Takes about a nanosecond. However now nancy isn't available anymore so betty gets one less option! We work down the list, always getting a shorter pick list.

However extremely often we run out of people to pick from. Imagine if frank gets jim, betty gets nancy and jim gets bob. Claire then can only get frank.

So what I currently do is put all this in a loop only stopping once we've made it all the way down the line and everyone is matched. But next year they'll each have three names in their lists. This can take a minute or more!

There has to be a better way to do this. I've looked around and thought it through and I can't work it out. Has anyone come accross a similar problem before? If so, please enlighten me!

In reply to Kris Kringle / Secret Santa by BigLug

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.