Shuffle

Random permutation of array elements, C-Mex: much faster than RANDPERM

Shuffle - Random permutation of array elements

This function is equivalent to X(RANDPERM(LENGTH(X)), but 50% to 85% faster. It uses D.E. Knuth's shuffle algorithm (also called Fisher-Yates) and the cute KISS random number generator (G. Marsaglia). While RANDPERM needs 2*LENGTH(X)*8 bytes as temporary memory, SHUFFLE needs just a fixed small number of bytes.

1. Inplace shuffling: Y = Shuffle(X, Dim)
INPUT:
X: DOUBLE, SINGLE, CHAR, LOGICAL, (U)INT64/32/16/8 array.
Dim: Dimension to operate on. Optional, default: 1st non-singleton dimension.
OUTPUT:
Y: Array of same type and size as X with shuffled elements.

2. Create a shuffle index: Index = Shuffle(N, 'index', NOut)
This is equivalent to Matlab's RANDPERM, but much faster, if N is large and NOut is small.
INPUT:
N: Integer number.
NOut: The number of output elements. Optional, default: N.
OUTPUT:
Index: [1:NOut] elements of shuffled [1:N] vector in the smallest possible integer type.

3. Derangement index:
Index = Shuffle(N, 'derange', NOut)
Equivalent to the index method, but all Index[i] ~= i. A rejection method is used: Create an index vector until a derangement is gained.

EXAMPLES:
R = Shuffle(1:8) % [8, 1, 2, 6, 4, 3, 5, 7]
R = Shuffle('abcdefg') % 'efbadcg'
R = Shuffle([1:4; 5:8], 2) % [3, 2, 1, 4; 6, 8, 7, 5]
I = Shuffle(8, 'index'); % UINT8([1, 5, 7, 6, 2, 3, 4, 8])
Choose 10 different rows from a 1000 x 100 matrix:
X = rand(1000, 100); Y = X(Shuffle(1000, 'index', 10), :);
Operate on cells or complex arrays:
C = {9, 's', 1:5}; SC = C(Shuffle(numel(C), 'index'));
M = rand(3) + i * rand(3); SM = M(:, Shuffle(size(C, 2), 'index'))

NOTES: There are several other shuffle functions in the FEX. Some use Knuth's method also, some call RANDPERM. This implementation is faster due to calling a compiled MEX file and it has a smaller memory footprint. The KISS random numbers are much better than the RAND() of the C-standard libs.

Run the unit-test TestShuffle to test validity and speed (see screenshot).
Tested: Matlab 6.5, 7.7, 7.8, 32bit, WinXP,
Compiler: LCC 2.4/3.8, BCC 5.5, Open Watcom 1.8, MSVC 2008.
Compatibility to 64 bit, Linux and Mac is assumed.
Pre-compiled Mex: http://www.n-simon.de/mex