From: "Derek O'Connor" <>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Derangement: efficient full permutation
Date: Fri, 18 Feb 2011 15:19:03 +0000 (UTC)
Organization: University College Dublin
Lines: 24
Message-ID: <ijm2l7$pco$>
References: <ii8ut8$3fb$> <ii90lg$qmd$> <> <iin0v4$ic2$> <iin5l5$h5n$> <iin77n$rje$> <iio9b0$m0i$> <ijk9se$gcb$> <ijlldg$181$> <ijln5n$o67$>
Reply-To: "Derek O'Connor" <>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: 1298042343 26008 (18 Feb 2011 15:19:03 GMT)
NNTP-Posting-Date: Fri, 18 Feb 2011 15:19:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 87230
Xref: comp.soft-sys.matlab:710914

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ijln5n$o67$>...
> "Derek O'Connor" wrote in message <ijlldg$181$>...
> > 
> > Also, remember that Roger's method uses at least twice as much memory as GRDrej and GRDsim, which becomes a problem for n > 10^8, with 16GB ram.
> >
> I just take a closer look of Roger's algorithm, and it looks like it is doable to work with a single array (in a C Mex coding). It is also possible to plug a O(N) shuffle engine for it.
> Bruno



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.