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: Fri, 18 Feb 2011 15:19:03 +0000 (UTC) Organization: University College Dublin Lines: 24 Message-ID: <ijm2l7$pco$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> 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 1298042343 26008 172.30.248.37 (18 Feb 2011 15:19:03 GMT) X-Complaints-To: news@mathworks.com NNTP-Posting-Date: Fri, 18 Feb 2011 15:19:03 +0000 (UTC) X-Newsreader: MATLAB Central Newsreader 87230 Xref: news.mathworks.com comp.soft-sys.matlab:710914 "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ijln5n$o67$1@fred.mathworks.com>... > "Derek O'Connor" wrote in message <ijlldg$181$1@fred.mathworks.com>... > > > > > 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 ---------------------- 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. Derek