Marc LeBrun wrote:
OK, tastes differ. I don't recall any restriction to n-cycles. I actually enjoy the craziness of not knowing what size cycle you will wind up in.
Since yesterday, I've taken an unscientific poll. My desire for n-cycles is clearly in the minority, so I'll abandon it. Many people agreed with you completely, seeing the small cycle possibility as a feature, not a bug. Some had a third option entirely: ideally, there should be no 2-cycles, but anything else is fine.
Your method will work fine for n-cycles. In fact, more simply, since we basically hide the random permutation by leaving the envelopes face down during the shift step, we might as well just write our names in the clear on the fronts as well.
Oof, right, I knew I had an extra layer of complexity in there -- a vestige of an earlier scheme I'd been thinking of. Thank you.
Although this is mechanically a smidgen trickier than just drawing names, and might be cleverly improved somehow, I think it's conceptually comparable since the ephemeral global information still is just a single random permutation.
Good, glad it passes the test of having the right smell for a solution.
Now what about those pesky derangements?
Okay, this shouldn't be too bad. There is an easy *almost* correct answer. One so-so way to generate a random derangement a_1, a_2,..., a_n is as follows: --------- 1) Start with all a_i = i 2) For i from 1 to n-1, swap the value of a_i with one of a_{i+1},...,a_n, chosen at random --------- This can easily be modified into the desired type of blind generation scheme: --------- 1) Each person writes her own name on a piece of paper, folds it, puts it in an envelope, and writes her own name on the outside of the envelope in such a way that if you fold the flap over backwards, it covers up her own name. Put all these anonymized envelopes into the hat. 2) Pick a random pair of envelopes out of the hat, swap the pieces of paper inside them, then put *one* of them back into the hat. The other one is finished: unfold its flap to reveal whose envelope it is and give it to them; the name inside is the person they give gifts to. Keep this up right through swapping the contents of the last two envelopes. --------- It's easy to see that no one gives themselves gifts: the first time my envelope gets drawn from the hat, my name is removed from it, and then either my envelope or my name is immediately out of circulation. This is so-so because it doesn't generate derangements uniformly at random. Since we picked envelopes in a random order, no particular person is treaded asymmetrically, of course! But some cycle structures are more or less likely than they "ought" to be. I haven't tried to analyze it in detail, but I suspect you get too few 2-cycles, for example. Probably the person who is handed their envelope in the first pass through step 2 can make some guesses as to the length of the cycle they're in. Anyone want to really do this calculation? It might be interesting... I'll have to think more about whether there's an easy variant that will give uniform distribution to the derangements generated --- without giving out more information. (I may have one that will give all derangements but where the people watching will know the number of disjoint cycles, for example.) --Michael Kleber kleber@brandeis.edu