File Exchange

## RANDPERMFULL

version 4.0.0.1 (2.35 KB) by
RANDPERMFULL (N) returns a random derangement (complete permutation) of the integers from 1 to N

1 Download

Updated 23 May 2019

View License

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

### Cite As

Jos (10584) (2021). RANDPERMFULL (https://www.mathworks.com/matlabcentral/fileexchange/30189-randpermfull), MATLAB Central File Exchange. Retrieved .

### Comments and Ratings (10)

Jos (10584)

Oops!!!! Thanks Vincent! I've update the function.

Vincent Lemaire

Does not exclude the violation R(N)=N.
For example, randpermfull(3) can output [2,1,3], which is a violation

Jos (10584)

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

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

Jan

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

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.

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.

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

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

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?

##### MATLAB Release Compatibility
Created with R2018a
Compatible with any release
##### Platform Compatibility
Windows macOS Linux

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!