shuffling

shuffling does a random permutation of the elements of input vector

Syntax

• x=shuffling(x)example

Description

 x =shuffling(x) shuffling applied to a set of 20 elements.

Examples

expand all

shuffling applied to a set of 20 elements.

shuffling(1:20)
ans =

Columns 1 through 13

18    11     7     8    13    10    12     9    20     5    16    15    17

Columns 14 through 20

19     6    14     4     3     2     1



Related Examples

expand all

shuffling applied with parsimonious data type.

shuffling applied to a set of 20 elements, but using a parsimonious data type; this is convenient if the vector is big.

shuffling(int8(1:20))

check of the permutation produced by shuffling.

x = 1:200000;
numel(unique(shuffling(x)))

Computation time of shuffling and randperm.

An extensive test for various sample sizes.

% REMARK: shuffling code is interpreted whereas randperm is compiled;
% therefore, the comparison has to be done using tic-toc statements,
% as in the example below (the MATLAB profiler would over-estimate the
% shuffling time).
RefTime = 1;
for n = [10, 10^2, 10^3, 10^4, 10^5, 10^6, 10^7]
X = 1:n;
% Estimate the number of profiling loops:
iniTime = cputime;
countLoop = 0;
while cputime - iniTime < RefTime
Xp = X(randperm(n));
clear('Xp');   % Necessary to suppress JIT acceleration
countLoop = countLoop + 1;
end
nDigit = max(1, floor(log10(max(1, countLoop))) - 1);
nLoop  = max(4, round(countLoop / 10 ^ nDigit) * 10 ^ nDigit);
% monitor randperm
tic;
for i = 1:nLoop
Xp = X(randperm(n));
clear('Xp');
end
RandPermTime = toc;
% monitor shuffling
tic;
for i = 1:nLoop
Xp = shuffling(X);
clear('Xp');
end
ShufflingTime = toc;
% results
fprintf('\n%d elements shuffled %d times: \n', n, nLoop);
disp(['    - shuffling etime (seconds): ' num2str(ShufflingTime)]);
disp(['    - randperm  etime (seconds): ' num2str(RandPermTime)]);
fprintf('SHUFFLING TIME IS %.1f%% of RANDPERM TIME\n', 100.0 * ShufflingTime / RandPermTime);
end

Computation time of shuffling and randperm.

Now the sample size is chosen at random, between 1 and 1000000.

% Note that results can differ between MATLAB releases. See below.
stoc = 0; rtoc = 0; loops = 100; n = zeros(100,1);
for i=1:loops
n(i) = randi(1000000 , 1);
%n(i) = floor(1000000*abs(randn));
x = randi(1000000 , n(i) , 1);
nn=numel(x);
st = tic;
xperm1 = shuffling(x);
stoc = stoc+toc(st);
rt = tic;
ix = randperm(nn);
xperm2 = x(ix);
rtoc = rtoc+toc(rt);
clear('xperm1','ix','xperm2'); % Necessary to suppress JIT acceleration, for realistic times
end
disp(['shuffling etime (seconds): ' num2str(stoc)]);
disp(['randperm  etime (seconds): ' num2str(rtoc)]);
fprintf('==> SHUFFLING TIME IS %.1f%% of RANDPERM TIME\n', 100.0 * stoc / rtoc);
% Results on R2016b
%     shuffling etime (seconds): 4.5303
%     randperm  etime (seconds): 5.3804
%     ==> SHUFFLING TIME IS 84.2% of RANDPERM TIME
% Results on R2012a
% shuffling etime (seconds): 7.9629
% randperm  etime (seconds): 4.9526
% ==> SHUFFLING TIME IS 160.8% of RANDPERM TIME
% Results on R2009a
% shuffling etime (seconds): 8.4239
% randperm  etime (seconds): 9.5947
% ==> SHUFFLING TIME IS 87.8% of RANDPERM TIME

Input Arguments

x — A set of elements. Vector of length t.

Data Types: single|double

Output Arguments

x —A permutation of the set of elements in x.  Vector of length t

Data Types - single|double

If set $x$ has $t$ elements, the objective is to obtain each of the $t!$ pemutations with equal probability, especially when $t$ is large. To achieve this goal we use backward Knuth's shuffling, which is based on the Fisher-Yates shuffle.

shuffling has been introduced as an alternative to MATLAB function randperm. Randperm makes a call to sort(rand(1,n)) and, overall, is slower than shuffling (for example, in R2009a shuffling was on average 25 faster). If compiled as mex file, shuffling becomes much more efficient than x(randperm(numel(x))) solution (it is about 60 faster for n=10^6). C code that can be used for this purpose is available at the http://it.mathworks.com/matlabcentral/fileexchange/27076-shuffle website as part of Jan Simon's Shuffle library.

References

Knuth, D.E. (1969), "The Art of Computer Programming volume 2, Seminumerical algorithms", Reading, MA: Addison-Wesley, pp. 124-125.

Fisher, R.A. and Yates, F. (1948), "Statistical tables for biological, agricultural and medical research (3rd ed.)", Oliver & Boyd, pp. 26-27.