View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from

Be the first to rate this file! 4 Downloads (last 30 days) File Size: 2.71 KB File ID: #30189 Version: 3.0



Jos (10584) (view profile)


26 Jan 2011 (Updated )

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

| Watch this File

File Information

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.
% 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}) '?'])


MATLAB release MATLAB 7.11 (R2010b)
MATLAB Search Path
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 (8)
25 Feb 2016 Jos (10584)

Jos (10584) (view profile)

The most recent version (partially) overcomes the three problems rightfully mentioned by Derek.

Comment only
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)) ;

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

Comment only
28 Jan 2011 Jan Simon

Jan Simon (view profile)

@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.

Comment only
27 Jan 2011 Bruno Luong

Bruno Luong (view profile)

@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.

Comment only
27 Jan 2011 Jos (10584)

Jos (10584) (view profile)

@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.

Comment only
27 Jan 2011 Derek O'Connor


The latest version of the notes mentioned above are here:

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

Derek O'Connor

Comment only
27 Jan 2011 Derek O'Connor


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:

Derek O'Connor

Comment only
26 Jan 2011 Bruno Luong

Bruno Luong (view profile)

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?

Comment only
25 Feb 2016 3.0

improvement rejection algorithm

Contact us