From: "Derek O'Connor" <>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Derangement: efficient full permutation
Date: Mon, 7 Feb 2011 08:09:04 +0000 (UTC)
Organization: University College Dublin
Lines: 30
Message-ID: <iio9b0$m0i$>
References: <ii8ut8$3fb$> <ii90lg$qmd$> <> <iin0v4$ic2$> <iin5l5$h5n$> <iin77n$rje$>
Reply-To: "Derek O'Connor" <>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: 1297066144 22546 (7 Feb 2011 08:09:04 GMT)
NNTP-Posting-Date: Mon, 7 Feb 2011 08:09:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 87230
Xref: comp.soft-sys.matlab:708551

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <iin77n$rje$>...
> "Derek O'Connor" wrote in message <iin5l5$h5n$>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message 
> > 
> > I assume (hope?) this uniformity continues for much higher values
> > of n, where such testing is impossible.
> > 
> I think that observation can be explained very well: for large n, derangement converges to permutation, and Jan Simon's converges to Knuth's. Though the small bias will be there.
> Bruno


I have tested GRDsim using your very useful TestBrunoGRDsim(n,ns) for n = 3.:20, and ns up to 10^7. In all tests GRDsim gave derangements, so it does not 'converge' to Durstenfeld's (Knuth) algorithm, which generates all possible permutations. Also, at n =
20, ns = 10^7, your test showed that the derangements were generated uniformly.

I was still intrigued by the strange behavior of GRDsim for n = 3:10 so I tested my GRDrej, which is 'provably correct', being based on GRPfys. I got exactly the same strange behavior!

Then I tested GRDmpp (Martinez et al.) and got the same behavior, converging to uniformity at about n = 12,13. 

This implied that the strange frequency behavior was coming from GRPfys, so I tested it with TestBrunoGRDsim(n,ns), n = 3:12, ns up to 10^7. Of course, only 37% of the permutations generated are derangements. But again, I got exactly the same strange behavior.

So it seems that the source of the strange frequency behavior for small values of n, is due to the Durstenfeld-Fisher-Yates algorithm. I have no idea why this is so. These small, combinatorial algorithms are still a mystery to me.

Bruno, I think we may have been arguing at cross purposes: I don't care about the behavior of GRPfys(n), GRDrej(n), and GRDsim(n), for n < 20, but you do.