OpenEuphoria

Re: Derangements

• Posted by "Christian Cuvier" <Christian.CUVIER at agriculture.gouv.fr> Jun 29, 2004
• 429 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