0
$\begingroup$

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.)

$\endgroup$
2
$\begingroup$

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 $2t$ permutations will always be at most $(2/3)^{2t} \le 2^{-t}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.