Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Derangement Generator

Subject: Derangement Generator

From: Derek O'Connor

Date: 20 Mar, 2011 00:02:04

Message: 1 of 1

I have just found this random Derangement generator that seems to be faster than other generators :
"An analysis of a simple algorithm for random derangements",
by D. Merlini, R. Sprugnoli and M. C. Verri, in Proc. of ICTCS 2007.

http://www.dsi.unifi.it/~merlini/papers/Derangements.pdf

Here is a Matlab version of their pseudo-Pascal algorithm , with some minor changes in variable names and the addition of two metering variables nw and nr.

------------------------------------------------------------
function p = GRDmsv(n);
% Generate a random derangement p(1:n).
% Derek O'Connor, Mar 19, 2011.

nw = 0; nr = 0;
derange = false;
while ~derange
     nw = nw+1;
     p = 1:n; % start with the identity permutation.
     k = n;
     fixedpt = false;
     finished = false;
     while ~finished
          r = ceil(rand*k); nr = nr+1;
                if (p(r) == k) % Early rejection
                        fixedpt = true;
                        finished = true;
                else
                        t = p(k);
                        p(k) = p(r);
                        p(r) = t;
                end
          k = k-1;
          if k == 1
                finished = true;
          end
     end % while ~finished
     if ~fixedpt && (p(1) ~= 1)
           derange = true;
     end
end % while ~derange
return; % GRDmsv
-----------------------------------------------------------

GRDmsv generates a random derangement p(1:n) using what I call "early rejection"
(the authors call it "early refusal").

The outer while-loop is the rejection loop. The inner while-loop is the Fisher-Yates-Durstenfeld shuffle algorithm which is aborted to the outer loop if a fixed point is
generated.

The authors prove that the expected number of calls to rand is E(nr) = n*(e-1) = 1.7183n rather than 2.718n for the pure rejection algorithm and 2n for the Martinez et al. algorithm.

Testing shows that the average number of outer while-loop iterations is
E(nw) = e = 2.718, the same as the pure rejection algorithm, but these loops are rejected early and so complete permutations are not built and then rejected. This accounts for the
lower number of calls to rand.

Here are some preliminary timing results:

Permutation length n = 10^6. Times(secs) averaged over 100 samples

GRDrej (Pure rejection) 0.56314
GRDmpp (Martinez, et al.) 0.29022
GRDsta (R.Stafford) 0.40402
GRDmsv (Merlini, et al.) 0.27693

Dell Precision 690, Intel 2xQuad-Core E5345 @ 2.33GHz
16GB RAM, Windows7 64-bit Professional. MATLAB Version 7.6.0.324 (R2008a)


See this thread for a discussion on derangement generators.
http://www.mathworks.com/matlabcentral/newsreader/view_thread/302075#820677

Derek O'Connor

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us