Finding all derangements

A derangement is a permutation p of such that no item in is in its proper position i.e p!=i for all i in <1...n> . Write an efficient program/algo to find all derangements of n items.

A brute force strategy would be to get all the n! permutation and check each for derangement. This would be a pathetic O(n!) algo.
However the search can be pruned to save a substantial iterations.
1. While getting a permutation if at any time a=i , discard the whole permutation and start fresh.

I expect any non brute force algo for this.

One approach that I can think of is:
Iteration(i=0 to N)

a=getRandom(0...n except i)

Iteration(j=0 to N)
if(j==i)
continue;
a[j]=getRandom(0...n except j or any other already placed already)

End Inner Iteration 

End Outer Iteration.

Not sure if I am missing something in this algo but if it is correct it is far better than brute force

One Response:

The total number of derangements is floor(n!/e).
Thus you cant expect an algo of complexity better than O(n!).

You can do better pruning of bruteforce algo though.