Algorithmic pseudo-random permutations for large sequences
% PERMDATA = createRandomPermutation(NUMOBJECTS, NROUNDS) generates a
% struct representing a pseudo-random permutation of the sequence
% 1:NUMOBJECTS.
%
% The permutation is generated algorithmically, so there is no need to
% hold it in memory. This is useful for pseudo-random permutations which
% are too large to be generated with randperm. The parameter NUMOBJECTS
% can be very large, provided that floating point arithmetic errors keep
% below 0.5 (for example, it works for the range 1:1e12).
%
% It is essentially a slow, quick-and-dirty implementation of a
% substitution-perturbation network (essentially a randomly generated,
% probably non-secure block cipher with custom block-length). Surely
% there are simpler ways to generate good pseudo-random perturbations,
% but I am no expert...
% See:
% http://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_cycle_walking
% http://en.wikipedia.org/wiki/Substitution-permutation_network
%
% The parameter NROUNDS specifies the number os stages of the network.
%
% Example: To generate a permutation of the sequence 1:1e8, first
% generate a random substitution-perturbation network (in
% this example, with 10 stages:
%
% permdata = createRandomPermutation(1e8, 10);
%
% Then, to generate the n-th element of the permuted sequence,
% use:
%
% m = permdata.encode(permdata, n);
%
% Example: create a random permutation of the sequence 1:10000 and check
% that it is, effectively, a permutation
%
% permdata = createRandomPermutation(10000, 10);
% x = (1:permdata.numobjects)';
% y = zeros(size(x));
% for k=1:numel(y);
% y(k) = permdata.encode(permdata, x(k));
% end
% yy = sort(y);
% isequal(x, yy)
% plot(x,y,'.'); grid on;
%
% Copyright (C) Jose David Fernandez Rodriguez 2012
Cite As
JD (2024). Algorithmic pseudo-random permutations for large sequences (https://www.mathworks.com/matlabcentral/fileexchange/36626-algorithmic-pseudo-random-permutations-for-large-sequences), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.
Version | Published | Release Notes | |
---|---|---|---|
1.0.0.0 |