Code covered by the BSD License

### Highlights fromRANDPERMFULL (derangement)

Be the first to rate this file! 2 Downloads (last 30 days) File Size: 2.2 KB File ID: #30189

# RANDPERMFULL (derangement)

26 Jan 2011

RANDPERMFULL (N) returns a random derangement (complete permutation) of the integers from 1 to N

File Information
Description

RANDPERMFULL(N) is a random complete or full permutation of the integers from 1 to N; each integer is randomly assigned to an index position that is different from its value. In other words R = RANDPERMFULL(N) creates a row vector R, such that R(j) ~= j for all j=1:N. This type of permutation is called a derangement.
N should be larger than 1.

Example:
randpermfull(7)
% might be [2 4 5 6 1 7 3], but not [2 1 3 6 4 7 5]
% since 3 cannot be in index position 3.

% Scramble a sentence
Words = {'can', 'you', 'make', 'sense', 'of', 'this', 'scrambled', 'sentence'} ;
R = randpermfull(numel(Words)) ;
disp([sprintf('%s ',Words{R}) '?'])

Reference: http://en.wikipedia.org/wiki/Derangement

MATLAB release MATLAB 7.11 (R2010b)
Other requirements Should work on ML releases that support [~, x] = notations. Otherwise, replace the ~ in the code by "dummy".
Tags for This File
Everyone's Tags
Tags I've Applied
28 Jan 2011

% a not so elegant rejection scheme
% it is quite fast but not so elegant

[tmp,R] = sort(rand(1,N)) ;
R0 = 1:N ;
while any (R == R0) % Derangement?
[tmp,R] = sort(rand(1,N)) ;
end

I find three problems with this method of generating derangements:

(1). The use of [tmp,R] = sort(rand(1,N)) to generate random
permutations is, to my eye, inelegant. Worse, it is inefficient because its complexity is O(NlogN). The Durstenfeld 1964 Algol implementation of the Fisher-Yates shuffle is O(N) and is, therefore, optimal up to a multiplicative constant. This is what
Jan Simon and I have used.

(2). It requires 2 or 3 times as much memory as the Durstenfeld algorithm. For example, with N = 5e8, my GRDrej required 6.5GB, Jan Simon's GRDmex 4.4GB, while randpermfull4 needed 14GB. The generation times were 187secs, 67secs, and 158secs, respectively. Note that GRDrej is pure Matlab, GRDmex is mexed, and randpermfull4 uses Matlab's built-in sort.

(3). The derangement test accounts for a small fraction of the time for each iteration of the while-loop. A simple loop over R to check if R(i)==i is sufficient. You have vectorized this test at the cost of an extra array R0, which accounts for some (4GB?) of the 14GB used in (2) above. Your vectorized test is elegant and is faster than the loop test, which takes 1.6 times longer on average. But it
is 1.6 times 5% of the total running time, so you have got a very minor speed-up at the cost of an extra large vector. To me, that is a bad trade-off.

Derek O'Connor

28 Jan 2011

@Jos: For large N this needs a lot of temporary memory.
Your function is about 4 times faster (e.g. for N=1e6) if you use the C-Mex SHUFFLE(N, 'index') instead of SORT(RAND(1,N)).
But including the rejection inside the fisher-yates shuffle should be much more efficient.

27 Jan 2011

@Derek. Thanks for the reference I'll take a look.
@Jos. Oh yeah, I expect the Martinez in MEX, that will be great. I reserve the five star rating for later then.

27 Jan 2011

@Bruno. I've implemented the Martinez algorithm (in Matlab) as well, but it is rather slow for large N. I am busy making a mex file out of it.

27 Jan 2011

Bruno,

http://www.scribd.com/doc/47228910/RPGLab-A-Matlab-package-for-Random-Permutation-Generation

I've posted an update to FEX but it seems to take quite a long time.

Derek O'Connor

27 Jan 2011

Bruno,

Martinez et al's algorithm is a rejection algorithm which makes it a Las Vegas algorithm: guaranteed to work but may take forever.

This algorithm and a simple rejection algorithm based on the Fisher-Yates Shuffle are implemented, and explained in the notes, here:

http://www.mathworks.com/matlabcentral/fileexchange/30101-rpg-tools

Derek O'Connor

26 Jan 2011

Humm, I rather like a non-rejection scheme. I'm not sure if I understood correctly Jos: Is there a flaw in Matinez's method that has been implemented?