Algorithm for mapping objects of list without mapping to itself?

Question

I want to map objects of a list, to objects of that same list, randomly, without ever mapping any given object to itself.

So given a list of objects [a, b, c] valid maps would be, for example:

 a -> b,
 b -> c,
 c -> a

or

 a -> c,
 b -> a,
 c -> b

an invalid mapping would be:

 a -> a,
 b -> c,
 c -> b

I just cannot figure out how to implement such an algorithm.

(This is for a small Secret Santa app that I am building where each person will be assigned to buy gift to one of the other participants.)

Answer 1

If you want a cyclic permutation with no trivial cycles (i.e., the only cycle involves all elements) see Sattolo's algorithm.

If you only want to avoid trivial cycles (but you are fine with cycles of length at least 2ドル$), the mathematical object is called a derangement.

See: https://math.stackexchange.com/questions/302057/generating-a-random-derangement

Since the probability $p_n$ that a random permutation on $n$ elements is a derangement approaches $\frac{1}{e}$ as $n \to \infty$, you can easily get a randomized algorithm by simply generating a random permutations (e.g., using Fisher-Yates shuffle) until you find a derangement.

The above bound is asymptotic but this works even for small values of $n$. This is because the number of derangements on $n \ge 2$ elements is $!n = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$ (see,e.g., here). Since $p_n = \frac{!n}{n!}$, we can explicitly compute $p_2 = \frac{1}{2}$, $p_3 = \frac{2}{6} = \frac{1}{3}$, and for $n \ge 4$ we have:

$$ p_n = \frac{!n}{n!} = \frac{\left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor}{n!} > \frac{\frac{n!}{e} - \frac{1}{2}}{n!} = \frac{1}{e} -\frac{1}{2 \cdot n!} \ge \frac{1}{e} -\frac{1}{2 \cdot 24} > \frac{1}{3}. $$

This shows that, on average, you will not reject more than 2ドル$ permutations. In general, the probability that you will look at more than 2ドルt$ permutations will always be at most $(2/3)^{2t} \le 2^{-t}$.