10
$\begingroup$

Motivation. In my younger son's class, everyone has to give a (small) Christmas present to one other student. Let $n\in\mathbb{N}$ be the number of students in the class. If you pick a permutation $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$ at random, there is a high probability, that we have at least one fixed point, that is a student who has to give to him- or herself, which is unacceptable, of course. Which gives rise to the following question.

Question. Given an integer $n>1$, is there a "simple enough" [1] process or algorithm that picks a fixed-point-free permutation $\varphi:\{1,\ldots,n\}\to\{1,\ldots,n\}$ with equal probability amongst all fixed-point-free permutations of $n$ elements?

[1] apologies for the hand-waving

Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ See for example math.stackexchange.com/questions/302057 $\endgroup$ Commented Nov 19 at 13:33
  • 3
    $\begingroup$ @FabiusWiesner When the last person picks, there might be only their own number in the urn. $\endgroup$ Commented Nov 19 at 14:30
  • 5
    $\begingroup$ The question as asked is not research level: the constructive proof of the recurrence $!n = (n-1)(!(n-1) + !(n-2))$ effectively gives an algorithm and dates back centuries. What might make it research level is to ask for an algorithm which can be performed without third parties and which leaves recipients without any information about who will be giving them a gift. I've seen this discussed on mathematical YouTube channels in the past year. $\endgroup$ Commented Nov 19 at 14:49
  • 4
    $\begingroup$ In fact, the probability of having at least one fixed point is asymptotically bounded away from 1 (precisely, it converges to $1-e^{-1}$). So the simplest approach is to generate a random permutation, and try again if it has a fixed point. With high probability this succeeds after a constant number of tries. $\endgroup$ Commented Nov 19 at 14:49
  • 4
    $\begingroup$ @SamHopkins, sure, I’m just correcting the OP’s comment that there is a fixed point with high probability. $\endgroup$ Commented Nov 19 at 15:03

2 Answers 2

Reset to default
11
$\begingroup$

This is not an answer to the mathematical question. But it is an answer to the practical problem, which, I think, is nice enough to be shared, and it doesn't fit in the comments.

Many years ago, a group of my friends asked ourselves this question, for the exact reason you give (distributing Christmas presents), and while all of us mathematicians and computer scientists were coming up with very complicated ideas, a non-mathematician came up with the following very simple procedure:

Each person chooses a random number. Then the numbers are sorted, and each person gives their present to the one with the next largest number (except the person who chose the largest number, who gives it to the smallest).

This does not, of course, pick a fixed-point-free permutation uniformly like you asked, but a cycle with maximal length, by choosing a conjugate of the obvious standard $n$-cycle.

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ As I already mentioned in a comment (now deleted, because it did not answer the question), a random $n$-cycle can be generated more easily by en.wikipedia.org/wiki/… . $\endgroup$ Commented Nov 19 at 14:39
  • 2
    $\begingroup$ Another practical solution: If the number of people is even, sort them into two colors, red and blue. Each person picks a random name of the other color. This produces a permutation drawn uniformly among all with no odd cycles. Can be easily be generalized for more than two colors. $\endgroup$ Commented Nov 19 at 14:42
  • 3
    $\begingroup$ @Numa This produces a permutation with no odd cycles weighted by $2$ raised to the power of the number of cycles, since for each even cycle there are $2$ ways to 2-color it. $\endgroup$ Commented Nov 19 at 15:03
  • 1
    $\begingroup$ Indeed, one can show $n! = \sum_{\sigma} 2^{\#cyc(\sigma)}$ bijectively (essentially MO:412727) where $\sigma$ ranges over all permutations with only even cycles. If you pick a random permutation $\pi$ and then run this bijection in reverse, then you get an even-cycle-only permutation $\sigma$ and a bitstring indexed by the number of cycles of $\sigma$. As an aside at the level of $S_n$-characters, let $B_n := \sum_{k=0}^{n/2} (-1)^k \chi^{(n-k,k)}$. It's not too difficult to show that $B_n(\sigma) = 2^{\#cyc(\sigma)}$ if $\sigma$ has only even cycles, 0 otherwise. $\endgroup$ Commented Nov 20 at 5:35
  • 2
    $\begingroup$ The practical Secret Santa problem has some privacy desiderata that are addressed in the paper Discreet Solitary Games by Crépeau and Kilian. $\endgroup$ Commented Nov 20 at 22:03
1
$\begingroup$

There is a 1:1 correspondence between permutations and bipartite matching: person in their role as donors constitute to vertex set $A$ and persons in their role as recipients constitute to vertex set $B$.

Self-assignments can be avoided by not including edges that connect the same person as a donor with itself as a recipient.

Random permutations without self-assignments can be obtained by solving the perfect matching instance after having assigned random edge-weights, but weights that reflect some knowledge about the persons would also readily be possible.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.