Is there an efficient algorithm to find the i-th dearrangement? 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.
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)