Re: Derangements
- Posted by "Christian Cuvier" <Christian.CUVIER at agriculture.gouv.fr> Jul 02, 2004
- 431 views
> Date: Thu, 01 Jul 2004 19:53:17 +0200 > From: "Juergen Luethje" <j.lue at gmx.de> > Subject: Re: Derangements > > > Christian Cuvier wrote: > > >>> <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: >>> > <snip> > > Hi, that's interesting. But I believe that the code contains a bug. > The following snippet just prints '{}' 5 times: > > }}} <eucode> > for n = 3 to 7 do > ? allDerangements(n) > end for > </eucode> {{{ > You're right, the init code is wrong. Here's something better I think:
function allDerangements(integer n) --returns a sequence of all derangements of {1,...,n} sequence res,res2 if n<2 then return {} end if if n=2 then return {{2,1}} end if res=repeat({2},n-1) for i=3 to n do res[i-1]={i} end for for i=2 to n do res2={} for j=1 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
Also, length(allDerangements(n))/n! is the alternating sum of the 1/k!, 0 <= k <= n. Thus, the limit value is still 1/e and the maximum is 1/2, but the sequence oscillates towards its limit. Minimum is 1/3 (n=3). This alone may prevent any kind of direct indexing like Unkmar seemed to wish. If you don't care for all derangements, but only want to generate a random one, use the following algo: - n belongs to a cycle. rand() its length, then all its elements successively. To do so, draw an integer between 1 and n-1, then between 1 and n-2, etc, and successively map [1..p] to the set of the p integers not drawn yet. The length should not be n-1 nor 1. - Now, the integers not drawn have to be deranged. Repeat the above procedure startint from the highest available integer. You get a sequence of cycles, each of them deranging some piece of a partition of [1..n]. When the pool of available integers is exhausted, you are left with a valid result. - Since rand() is deterministic, controlling the rand_seed allows you to control reproducibility. The algorithm above is simple, but tricky to code if one is to implement the mappings efficiently. Tell me if you want me to code this. CChris > Regards, > Juergen