Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Derangement: efficient full permutation
Date: Fri, 18 Feb 2011 15:53:04 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 20
Message-ID: <ijm4l0$89i$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> <iio9b0$m0i$1@fred.mathworks.com> <ijk9se$gcb$1@fred.mathworks.com> <ijlldg$181$1@fred.mathworks.com> <ijln5n$o67$1@fred.mathworks.com> <ijm2l7$pco$1@fred.mathworks.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1298044384 8498 172.30.248.38 (18 Feb 2011 15:53:04 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 18 Feb 2011 15:53:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:710928

"Derek O'Connor" wrote in message <ijm2l7$pco$1@fred.mathworks.com>...

> 
> I have just noticed that I omitted the average time for GRDsta2mex, which is Roger's second method with randperm replaced by Jan's GRPmex.
> 
> GRDsta2mex:  0.21258 secs,  which is more that twice GRDmex, i.e., GRDrej with GRPmex.
> 
> Can you tell me exactly what is wrong with Jan's new derangement algorithm and give me counter-examples that I can test or examine. 
> 
> Please remember, I am not interested in n < 20. I am interested in generating random permutations of various types with n >> 10^6.

Derek, why arguing back and forth I think I have clearly elaborated my position.

You are free to trust Jan's algorithm at larger n with experimental testing. That's after all your choice.

Here are the facts that I stick with:
1) It's unproven algorithm.
2) It's biased at small n.

Bruno