Kris Kringle

Our family is breaking with our old everyone-buys-a-gift-for-everyone tradition this year and doing Kris Kringle instead. There’s a bit of kerfuffle about how to select names and get word out to everyone; I mentioned to wifey that the cleanest way would be to write a short program to shuffle the names and send each person a private email. This probably isn’t going to happen at this stage, but I might suggest it for next year. (Should go down well.)

In the meantime, it got me thinking about how to deal with people drawing their own name, which anecdotally seems to happen at least once without fail. I brute-forced some statistics, and the probability of someone not drawing their own name in any given run seems to approach e-1:

 1:        0 of        1 = zero
 2:        1 of        2 = 1 in 2.000000000000
 3:        2 of        6 = 1 in 3.000000000000
 4:        9 of       24 = 1 in 2.666666666667
 5:       44 of      120 = 1 in 2.727272727273
 6:      265 of      720 = 1 in 2.716981132075
 7:     1854 of     5040 = 1 in 2.718446601942
 8:    14833 of    40320 = 1 in 2.718263331760
 9:   133496 of   362880 = 1 in 2.718283693893
10:  1334961 of  3628800 = 1 in 2.718281657666

In other words, there’s about a 63% chance that at least one person will pick their own name and have to redraw. (There’s a 1/n chance that it’ll be the last person, which really screws things up.)

One way to avoid this if we end up doing it programmatically – other than re-shuffling until it works – is to shuffle the list of names, then assign everyone to buy a gift for the person after them in the (cyclic) list. This guarantees nobody getting their own name (for n > 1), and also has the property that there are no disjoint sets of people – everyone is in one cycle, rather than, say, two people buying for each other, or some number of larger cycles.

That seems more festive somehow. Also, it’s an actual advantage of doing it the geek way, since I can’t think of a way of doing it manually; which means I might actually be able to convince everyone that it’s a good idea.

Okay, here’s how you’d do to do it manually. Shuffle some playing cards, one for each person. Everyone takes a card, remembers it (without showing anyone), and writes their name on the back. Take the cards back, shuffle them again, and lay them out in a circle, face up. Everyone goes out of the room. One at a time, each person comes into the room (with nobody else watching), finds their own card, picks up the card clockwise from it and reads the name on the back.

Of course, my way prevents cheating.



    June 24, 2014 @ 6:26 pm

    For newest news you have to go to see the web
    and on the web I found this site as a finest website for most recent updates.

  2. urnext.Com

    June 25, 2014 @ 11:02 am

    Howdy, I do think your web site could be having web browser compatibility issues.

    Whenever I look at your website in Safari, it looks fine however, when opening in IE, it’s got some overlapping issues.

    I merely wanted to provide you with a quick heads up! Aside from that, wonderful blog!

  3. megapolis Hack

    June 25, 2014 @ 11:31 am

    Hi, its nice paragraph concerning media print, we all be familiar with media is
    a great source of data.

  4. lose weight fast

    June 25, 2014 @ 7:47 pm

    I’ve been surfing online greater than 3 hours lately, but I never found any attention-grabbing article like yours.
    It’s pretty price enough for me. Personally, if all webmasters
    and bloggers made good content as you probably did, the internet will probably
    be a lot more useful than ever before.

  5. marquee hire news articles

    June 25, 2014 @ 8:35 pm

    By way of comparison, the Ninth also defined what people do think makes someone an author:
    “someone who sits down at a desk with pen and paper and writes something”.
    Parties interested in booking helicopter charter and landings for the
    2012 FORMULA 1 UNITED STATES GRAND PRIX’, should contact Charlie Bravo Charter at charter@wepushtin. He still had the feeling that he was quickly becoming a last resort.

  6. ups website

    June 27, 2014 @ 4:06 pm

    Hi there, You’ve done a fantastic job. I’ll certainly digg it and personally recommend to my
    friends. I’m confident they will be benefited from this

  7. ダコタバッグ 人気

    June 28, 2014 @ 8:33 pm

    We are a group of volunteers and starting a new scheme in our community.

    Your web site provided us with valuable information to work on. You’ve done an impressive job and our
    whole community will be grateful to you.

  8. Http://

    July 1, 2014 @ 10:19 am

    This piece of writing will help the internet users for setting up new blog or even a blog from start to end.

  9. work at home for free

    July 8, 2014 @ 10:31 pm

    Definitely believe that which you said. Your favorite reason appeared to be on the net the easiest thing
    to be aware of. I say to you, I certainly get annoyed while people consider worries that they
    just don’t know about. You managed to hit the nail upon the top and also defined out the whole thing without having side effect , people can take a signal.
    Will likely be back to get more. Thanks

  10. Fort Lauderdale Realtors

    July 18, 2014 @ 10:53 am

    I do agree with all of the ideas you’ve introduced on your post.

    They’re very convincing and can certainly work.
    Nonetheless, the posts are very short for starters.
    Could you please lengthen them a bit from subsequent time?
    Thanks for the post.

  11. magnesium supplements

    July 19, 2014 @ 6:51 am

    We’re a gaggle of volunteers and opening a
    brand new scheme in our community. Your web site provided us with useful info
    to work on. You have performed a formidable process and our whole community can be grateful to

  12. Best Seo company

    July 22, 2014 @ 6:33 pm

    If you wish for to grow your knowledge simply keep visiting this web
    page and be updated with the hottest gossip posted here.

  13. testosterone supplement review

    July 27, 2014 @ 12:04 pm

    If you wish for to improve your know-how only keep visiting
    this website and be updated with the most recent gossip posted here.

  14. Anti-Aging Skin Care Product Reviews

    July 28, 2014 @ 3:07 am

    Hey I know this is off topic but I was wondering if you knew of any widgets I
    could add to my blog that automatically tweet my newest twitter updates.

    I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have some experience with something like this.
    Please let me know if you run into anything.
    I truly enjoy reading your blog and I look forward to your new updates.

  15. good dieting foods

    August 7, 2014 @ 9:38 pm

    This site was… how do you say it? Relevant!! Finally I’ve found something
    that helped me. Thanks a lot!


    September 25, 2014 @ 1:14 am

    Nice post. I was checking continuously this blog and I
    am impressed! Extremely useful info specifically the
    last part :) I care for such information much. I was looking for
    this particular information for a long time. Thank you
    and good luck.

  17. home

    December 1, 2014 @ 4:12 pm

    excellent points altogether, you just won a emblem new reader.
    What might you recommend in regards to your post that
    you just made some days in the past? Any sure?

  18. Adrenalast

    December 11, 2014 @ 1:00 pm

    May I simply just say what a relief to discover somebody that
    really understands what they are talking about online.
    You certainly know how to bring a problem to light and make it important.

    More people must read this and understand this side of the story.
    I was surprised you’re not more popular because you
    certainly possess the gift.

  19. Lifeforce Energy

    December 11, 2014 @ 1:36 pm

    This paragraph provides clear idea in favor of the new users of blogging,
    that genuinely how to do blogging.

  20. svelme

    December 12, 2014 @ 3:01 am

    It’s remarkable designed for me to have a web site, which is
    good in support of my knowledge. thanks admin

  21. Full MP3 Song

    January 3, 2015 @ 10:14 pm

    My family members all the time say that I am killing
    my time here at net, but I know I am getting knowledge everyday
    by reading such fastidious posts.

  22. Kitty

    January 8, 2015 @ 8:32 pm

    Great beat ! Iwish to apprentice whilst you amend your site, how
    can i subscribe for a weblog site? The account aided me a applicable deal.

    I were tiny bit acquainted of this your broadcast offered vivid transparent idea

  23. loto grecia draw

    January 9, 2015 @ 11:42 pm

    This is usually to emphasize the truth that somebody has won and also
    to promote others to play. This is accustomed to establish the free lucky Keno numbers.

    Stick forr your limits so you’re able to always enjoy each game without getting too stressed about your cash.

  24. kino grecia

    January 11, 2015 @ 5:46 pm

    Its popularity gained and it also made its way into Eufope where a few
    of the riles and characters used were changed to suit Western players.

    The detaikls regarding certain games are not only foiund
    about foibles, butt on strategies that can separate from thhe numerouss others that lose their lunch and mortgage
    in gamkes of luck. The keno draw will become in accordance with the scheduled time.

  25. Etsuko

    January 24, 2015 @ 11:23 am

    I’m really enjoying the theme/design of your blog.

    Do you ever run into any internet browser compatibility problems?
    A few of my blog audience have complained about my site not working correctly in Explorer but looks
    great in Chrome. Do you have any solutions to help fix this problem?


    February 2, 2015 @ 9:32 am

    I go to see each day some web sites and blogs
    to read articles, however this blog offers quality based


    February 19, 2015 @ 9:48 am

    Hey, I think your website might be having browser compatibility issues.

    When I look at your blog in Ie, it looks fine but when opening in Internet Explorer, it has
    some overlapping. I just wanted to give you a quick heads
    up! Other then that, superb blog!

  28. Valentina

    May 18, 2015 @ 11:37 pm

    The vudoo spell caster was there to reassure me and to ensure my financial life was

  29. Lucienne

    August 27, 2015 @ 6:42 pm

    “) Contact the Prometric Candidate Services Call Center at 800-696-2722 or Prometric. Those are some of the important characteristics that you want to look for as you’re searching for a CPA. Studies currently have shown which, about average, CPAs earn 10% more than non-CPA Accountants.

Leave a Comment