Code covered by the BSD License  

Highlights from
RANDPERMFULL (derangement)

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

RANDPERMFULL (derangement)

by

 

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

| Watch this File

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   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (7)
28 Jan 2011 Derek O'Connor

This latest version (4?) of RANDPERMFULL is:

% 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 Jan Simon

@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 Bruno Luong

@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 Jos (10584)

@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 Derek O'Connor

Bruno,

The latest version of the notes mentioned above are here:

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 Derek O'Connor

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 Bruno Luong

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?

Contact us