<p>Actually this is might be good question but it is badly formulated in its current form. The well-known algorithms for generating random derangements have linear expected time, but maybe it's an open problem to find a worst case polynomial time algorithm.</p>

<p>See for example:
<a href="http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf">http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf</a> (and slides: <a href="http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf">http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf</a>)</p>

CC BY-SA 3.0
2012-12-10T01:13:00.367Z
This seems like the right answer to me.
Suresh Venkat
CC BY-SA 3.0
2012-12-10T03:16:34.163Z
Doesn't the recurrence !n=(n−1)(!(n−1)+!(n−2)) described in http://en.wikipedia.org/wiki/Derangement immediately lead to a worst-case polynomial algorithm for random generation?
David Eppstein
CC BY-SA 3.0
2012-12-10T14:37:47.743Z
Yes, you are right. I was thinking there is a small catch because you have to be able to generate random numbers in arbitrary subsets of {1,...,n} in worst-case polytime, but that's easy to do.
didest
CC BY-SA 3.0
2012-12-10T01:08:45.600Z
2012-12-10T01:08:45.600Z
didest
<p>Why not, for each position <em>i</em>, randomly choose from all elements other than <em>i</em>? For example, you could choose an index into the original array from <em>[0..n-2]</em>, and if you get <em>j >= i</em> you use <em>j+1</em>.</p>

CC BY-SA 3.0
2012-12-09T23:39:36.113Z
Does that make all derangements equally likely?
David Eppstein
CC BY-SA 3.0
2012-12-09T23:59:09.917Z
oh, good point - this would place elements later in the array preferentially earlier in the array. If you were to fill slots in the target array in a random order all derangements would then be equally likely (by symmetry).
pat
CC BY-SA 3.0
2012-12-09T23:26:25.380Z
2012-12-09T23:26:25.380Z
pat
<p>Here is the background for this question. Friends and I were playing a game where everyone needs to give another people some gift. In order to determine who should give gift to whom, we decide to drew lots. But the problem is, someone might end up giving him/herself gifts, which is not funny. You can see that the expected number of such unfortunate people is 1, so this happens quite frequently.</p>

<p>For this purpose, dearrangement seems to be a great fit. If I can fairly generate a dearrangement, then I can just pick one dearrangement and use it to decide who give whom gifts.</p>

<p>Randomized dearrangement generation could be done with Las Vegas method. But the problem is,
it only has expected polynomial running time. So I came to this problem of finding i-th dearrangement. If I can randomly pick an i in [1, D_n], and use some worst case polynomial time (efficient) algorithm to obtain the i-th dearrangement, then it's done.</p>

CC BY-SA 3.0
2012-12-10T04:43:21.737Z
Could you please explain the motivation for the question? i.e. why are you interested in this question?
Kaveh
CC BY-SA 3.0
2012-12-11T23:01:28.260Z
Perhaps you want to play secret santa and aren't willing to take any chances :)
Lev Reyzin
CC BY-SA 3.0
2012-12-27T02:14:46.207Z
Could you add a line about what you mean by dearrangement?
Vijay D
<permutations>
Is there an efficient algorithm to find the i-th dearrangement?
Santa Zhang
# Is there an efficient algorithm to find the i-th dearrangement?

(Asked by: username_0 on 2012-12-09)

Here is the background for this question. Friends and I were playing a game where everyone needs to give another people some gift. In order to determine who should give gift to whom, we decide to drew lots. But the problem is, someone might end up giving him/herself gifts, which is not funny. You can see that the expected number of such unfortunate people is 1, so this happens quite frequently.

For this purpose, dearrangement seems to be a great fit. If I can fairly generate a dearrangement, then I can just pick one dearrangement and use it to decide who give whom gifts.

Randomized dearrangement generation could be done with Las Vegas method. But the problem is,
it only has expected polynomial running time. So I came to this problem of finding i-th dearrangement. If I can randomly pick an i in [1, D\_n], and use some worst case polynomial time (efficient) algorithm to obtain the i-th dearrangement, then it's done.

**Tags:** permutations

> **Comments:**
> **username_1**: Could you please explain the motivation for the question? i.e. why are you interested in this question?  
> **username_2**: Perhaps you want to play secret santa and aren't willing to take any chances :)  
> **username_3**: Could you add a line about what you mean by dearrangement?  

---

## 2 answers

### Answer by username_4 on 2012-12-10. Score: 9

Actually this is might be good question but it is badly formulated in its current form. The well-known algorithms for generating random derangements have linear expected time, but maybe it's an open problem to find a worst case polynomial time algorithm.

See for example:
<http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf> (and slides: <http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf>)

> **Comments:**
> **username_5**: This seems like the right answer to me.  
> **username_6**: Doesn't the recurrence !n=(n−1)(!(n−1)+!(n−2)) described in http://en.wikipedia.org/wiki/Derangement immediately lead to a worst-case polynomial algorithm for random generation?  
> **username_4**: Yes, you are right. I was thinking there is a small catch because you have to be able to generate random numbers in arbitrary subsets of {1,...,n} in worst-case polytime, but that's easy to do.  

---

### Answer by username_7 on 2012-12-09. Score: 0

Why not, for each position *i*, randomly choose from all elements other than *i*? For example, you could choose an index into the original array from *[0..n-2]*, and if you get *j >= i* you use *j+1*.

> **Comments:**
> **username_6**: Does that make all derangements equally likely?  
> **username_7**: oh, good point - this would place elements later in the array preferentially earlier in the array. If you were to fill slots in the target array in a random order all derangements would then be equally likely (by symmetry).  

---

