Timeline for Secret Santa (expected no of cycles in a random permutation)
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2010 at 9:37 | vote | accept | Chris Taylor | ||
| Dec 22, 2010 at 9:36 | comment | added | Chris Taylor | Thanks for your comment John. Rejection sampling was exactly what I was doing. Thankfully 1/e of randomly generated permuations are derangements, so it doesn't take too long. | |
| Dec 21, 2010 at 22:47 | answer | added | Douglas Zare | timeline score: 5 | |
| Dec 21, 2010 at 21:20 | answer | added | fedja | timeline score: 3 | |
| Dec 21, 2010 at 17:17 | answer | added | Peter Shor | timeline score: 14 | |
| Dec 21, 2010 at 16:59 | answer | added | Omer | timeline score: 6 | |
| Dec 21, 2010 at 11:27 | answer | added | john mangual | timeline score: 2 | |
| Dec 21, 2010 at 11:01 | comment | added | john mangual | Naturally, in Secret-Santa there nobody is giving gifts to themselves... How are you generate permutations without fixed points? One way is to rejection-sample a random permutation and discard if it has fixed pts... | |
| Dec 21, 2010 at 10:34 | answer | added | Qiaochu Yuan | timeline score: 7 | |
| Dec 21, 2010 at 10:27 | history | asked | Chris Taylor | CC BY-SA 2.5 |