(Sorry for missing much of this exciting discussion.  My e-mail server 
is having a bad hair day...)

On Oct 3, 2004, at 5:12 PM, Gavin Kistner wrote:

> On Oct 3, 2004, at 9:54 AM, James Edward Gray II wrote:
>> $santas = $players.sort_by { rand } until check_families?
>
> Does this actually work? I mean, for realistic data sets?

Excellent question.  I have no idea.  It does solve all the little 
examples I've thrown at it reasonably fast, but "realistic data sets" 
is pretty wide open.  This is the first of three solutions I came up 
with and not my favorite.  All of my ideas have now been represented by 
submissions.

What are the goals of a Secret Santa draw?  Randomness should be up 
there, I think.  This does handle that.  However, if speed also makes 
the list, this falls off the wagon.

> Perhaps my math is wrong

The essence of your message is right on, I think.  Naturally a random 
sort is an awful performer.

> your test case small

I've been using real life test cases and yes, they are pretty small.

> your computer really fast

Dual 2.0 G5, it's pretty fast.

> or your test case not pathological :)

Again, I'm using real life test data.  You're pathological case doesn't 
happen to model my friends well, but I don't know that that makes it 
less valid.

James Edward Gray II