Code covered by the BSD License  

Highlights from
Unique random permutations

Unique random permutations

by

 

Random sample (without replacement) from unique permutations of a vector or row-perms of a matrix

nchoosek_m(n, k, m)
function comb = nchoosek_m(n, k, m)
%nchoosek_m: efficiently compute the mth combination of nchoosek(1:n, k)
% comb = nchoosek_m(n, k, m)
%
% Examples:
%  first = nchoosek_m(10, 4, 1) % the "first" combination: [1 2 3 4]
%  last  = nchoosek_m(10, 4, nchoosek(10,4)) % the "final" comb: [7 8 9 10]
%  M = nchoosek(10, 4); rnd = nchoosek_m(10, 4, randi(M)); % random comb
%
% Motivation: nchoosek_m can be used to sample a few m with any k from
% n up to 53, easily ensuring no duplicates are sampled. In contrast,
% nchoosek(1:n, k) becomes time and memory expensive for n over about 30,
% e.g. combs = nchoosek(32, 16) takes over 2GB of memory.
%
% Note: this function is not reliable for n > 53. For speed reasons, this
% eventuality is not even checked, so be careful!
%
% See also: nchoosek, uperms, perms_m, signs_m, sample_no_repl

% Copyright 2010 Ged Ridgway
% http://www.mathworks.com/matlabcentral/fileexchange/authors/27434

comb = zeros(1, k);
i = 1; % ith element of requested comb
for c = 1:n % candidate for ith element (combs ordered lowest first)
    M = nchoosek_fast(n - c, k - i); % number of combs of higher elements
    if m <= M % are we within the set of combs starting with this c?
        comb(i) = c;
        i = i + 1;
        if i > k; return; end
    else
        m = m - M;
    end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function nck = nchoosek_fast(n, k)
%nchoosek_fast -- faster alternative to MATLAB version (no input checks)
nck = round(prod( (1+n-k:n) ./ (1:k) ));

Contact us