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.