RANDPERMFULL (N) returns a random derangement (complete permutation) of the integers from 1 to N
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
3.0 | improvement rejection algorithm |
Jos (10584) (view profile)
The most recent version (partially) overcomes the three problems rightfully mentioned by Derek.
Derek O'Connor (view profile)
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 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.
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.
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.
Derek O'Connor (view profile)
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 (view profile)
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 (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?