From: Gavin Kistner <gavin@...>
Date: 2004-10-04T07:12:06+09:00
Subject: Re: [SOLUTION] Secret Santas (#2)

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?

With the pathological case (where half the people are in the same 
family) I think[1] that the chances of randomly picking a working 
layout for pool size N are

N * ((N/2)-1)! / (N-1)!

If so, the chances of picking a working layout each time for a total 
pool of 4 people is 66.66%, the chances for a pool of 6 people is 10%, 
8 => 0.95%, 10 => .066%, and so on.

If my calculations are correct, by the time you reach 10 people in one 
family and 10 other participants, your chance of picking a working case 
drops to 6 in 100000000000. That's gotta take a long time to find a 
correct layout.

Perhaps my math is wrong, your test case small, your computer really 
fast, or your test case not pathological :)

- Gavin

[1] Statistics is not my strong suit. My reasoning is as follows:
Consider a pool of 6 participants:
Joe Smith
Jane Smith
Jim Smith
Bob Dole
Barbara Bush
Bill Clinton

The correct arrangement for this pathological case is an interleaving 
of Smiths and others, for example:
Jane Smith
Bill Clinton
Joe Smith
Bob Done
Jim Smith
Barbara Bush

There is a 1/1 chance that SOMEONE will be picked for the first spot.
There is a 3/5 chance that the next person will be of the opposite 
Smith/Non-Smith persuasion.
There is a 2/4 chance that the next person will be of the opposite 
Non-Smith/Smith persuasion.
There is a 2/3 chance for the next.
There is a 1/2 chance for the next.
There is a 1/1 chance for the last.
The cumulative chance of all that occurring is the product:
3/5 * 2/4 * 2/3 * 1/2 = 1/10

For an 8 person pool, the chances are:
4/7 * 3/6 * 3/5 * 2/4 * 2/3 * 1/2 = 1/35
Re-arranged, that looks like:
(4*3*3*2*2) / (7*6*5*4*3*2 )
which is
(4 * 3*2 * 3*2 ) / ( 7*6*5*4*3*2 )
which is
(4 * 2 * 3! ) / 7!

Looking at this pattern, then, the chances of randomly picking a 
working pattern for pathological pool size of N seems to be:

N/2 * 2 * ((N/2)-1)! / (N-1)! == N * ((N/2)-1)! / (N-1)!

Or, in Ruby:

class Fixnum; def factorial; t=1; 2.upto(self.to_i){ |i| t*=i }; t; 
end; end

def chances( pool_size )
   pool_size.to_f * (pool_size/2-1).factorial / (pool_size-1).factorial
end

40.times{ |i|
   next if i%2==1;
   puts "#{i} => #{chances i}"
}
0 => 0.0
2 => 2.0
4 => 0.666666666666667
6 => 0.1
8 => 0.00952380952380952
10 => 0.000661375661375661
12 => 3.60750360750361e-05
14 => 1.61875161875162e-06
16 => 6.1666728333395e-08
18 => 2.04044321691381e-09
20 => 5.96620823659007e-11
22 => 1.56257834767835e-12
24 => 3.70571940160874e-14
26 => 8.02905870348561e-16
28 => 1.60123677847291e-17
30 => 2.95794971392779e-19
32 => 5.08894574439191e-21
34 => 8.19243159608545e-23
36 => 1.23919133386167e-24
38 => 1.76761526601889e-26

(The 2.0 in the case of a pool size of 2 reflects that there are two 
correct cases, I think. Or perhaps it reflects the fact that my math is 
overly generous by a factor of 2 ;)