Path: news.mathworks.com!not-for-mail
From: "Derek O'Connor" <derekroconnor@eircom.net>
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$1@fred.mathworks.com>
References: <ii8ut8$3fb$1@fred.mathworks.com> <ii90lg$qmd$1@fred.mathworks.com> <590b82f4-743b-41f3-a43c-10ea68a644ce@e21g2000yqe.googlegroups.com> <iin0v4$ic2$1@fred.mathworks.com> <iin5l5$h5n$1@fred.mathworks.com> <iin77n$rje$1@fred.mathworks.com>
Reply-To: "Derek O'Connor" <derekroconnor@eircom.net>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1297066144 22546 172.30.248.37 (7 Feb 2011 08:09:04 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 7 Feb 2011 08:09:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 87230
Xref: news.mathworks.com comp.soft-sys.matlab:708551

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <iin77n$rje$1@fred.mathworks.com>...
> "Derek O'Connor" wrote in message <iin5l5$h5n$1@fred.mathworks.com>...
> > "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

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.

Regards,

Derek.