1
$\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.)

asked Nov 2, 2019 at 14:34
$\endgroup$

1 Answer 1

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

answered Nov 2, 2019 at 15:55
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.