Wednesday, April 22, 2009

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

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.