1. Re: Derangements
- Posted by "Christian Cuvier" <Christian.CUVIER at agriculture.gouv.fr> Jun 29, 2004
- 430 views
<Replying to Unkmar's request, a few days ago> I assume that "derangement" means "permutation without any fixed point". In this case, generating them is quite straightforward:
function allDerangements(integer n) --returns a sequence of all derangements of {1,...,n} sequence res,res2 if n<2 then return {} end if res={{2,1}} if n=2 then return res end if for i=3 to n do res2={} for j=i to length(res) do for k=1 to n do if k!=j and find(res[j],k)=0 then res2=append(res2,res[j]&k) end if end for end for res=res2 end for return res end function
Of course, this may be made faster. But remember that, if d_n is the length of the output for an input of n, d_n/n! decreases from 1/2 (n=2) to 1/e (about ...37) for large n. Thus, n=13 is probably the highest usable value, the problem being that length(res) may no longer fit into an integer. Sorry, but this generating algo does not easily allow to compute the index of a given derangement, or to find the derangement with a given index. What I know about is an indexing scheme for general permutations; I can post this if anyone is interested. CChris