OpenEuphoria

Re: Derangements

• Posted by "Christian Cuvier" <Christian.CUVIER at agriculture.gouv.fr> Jul 02, 2004
• 595 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