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.