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: Tue, 15 Feb 2011 12:24:04 +0000 (UTC) Organization: University College Dublin Lines: 33 Message-ID: <ijdr94$dog$1@fred.mathworks.com> References: <ii8ut8$3fb$1@fred.mathworks.com> <ijcp3v$4i2$1@fred.mathworks.com> Reply-To: "Derek O'Connor" <derekroconnor@eircom.net> NNTP-Posting-Host: webapp-05-blr.mathworks.com Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: fred.mathworks.com 1297772644 14096 172.30.248.35 (15 Feb 2011 12:24:04 GMT) X-Complaints-To: news@mathworks.com NNTP-Posting-Date: Tue, 15 Feb 2011 12:24:04 +0000 (UTC) X-Newsreader: MATLAB Central Newsreader 87230 Xref: news.mathworks.com comp.soft-sys.matlab:710127 "Roger Stafford" wrote in message <ijcp3v$4i2$1@fred.mathworks.com>... > "Jan Simon" wrote in message <ii8ut8$3fb$1@fred.mathworks.com>... > > Dear readers, > > An "derangement" is a permutation of the numbers from 1 to N such that no p(i)==i. If you use it to shuffle a vector, no element remains on the same position. > - - - - - - - - > I just noticed this interesting thread the other day and couldn't resist throwing in my two cents. The following is a non-rejection scheme that is calculated to have a uniform distribution over all possible derangement permutations of 1:n, that being the objection raised in this thread about Jan's code. > > Obviously a penalty is being paid for achieving this uniformity. This penalty relative to other methods would be less if it were rewritten so that many random derangements could be requested in a single call, since the probability vector below would only have to be computed once. > > It should be noted that the algorithm is O(n) so that for large n it might be competitive with rejection methods using an O(n*log(n)) sort operation. > > Roger Stafford > ----- snip -------------------- I have done some quick tests on your method (which I call GRDsta) and so far so good. Here is a comparison of normalized times Normalized Times: Four Derangement Generators. No. Samples = 10 ------------------------------------------------------------------ n GRDrej GRDsim GRDmpp GRDsta ---------------------------------------------------------------- 1e+005 1.1864 1 1.3028 1.3527 1e+006 1.7055 1 1.1602 1.4618 1e+007 1.8913 1 1.1876 1.3999 I have not analyzed it in detail, but my main criticism, so far, is that your method, GRDsta, uses 3 times as much memory as GRDrej and GRDsim: P = zeros(n-1,1); A = zeros(n,1); B = (1:n-1).'; Note that none of the other methods uses sorting, and that the provable expected running times for GRDrej and GRDmpp are 2.8*GRPfys and 2.0*GRPfys, respectively. I have shown experimentally that GRDsim is about 1.15*GRPfys. (See previous reply above). Do you have a detailed expected running time analysis of GRDsta? I'm trying to save myself some work. Regards, Derek O'Connor.