function a = randsubset_matlab(v, k)
% A = RANDSUBSET_MATLAB(N, K)
% 
% returns a random array A composed of K distinct and sorted elements of
% the set (1:N). The probablity of the subsets is uniform.
%
% A = RANDSUBSET_MATLAB(V, K), where V is a (cell) vector of length N,
% will pick K distinct elements of the set V. The elements of A respect the
% same order with respect to V.
%
% To get random sampling without replacement of the set, call RANDPERM
% after RANDSUBSET_MATLAB.
%
% The function uses Robert Floyd's sampling algorithm.
%
% See also: randperm, nchoosek, randsubset
% 
% Author: Bruno Luong
% Original: 24-Jun-2010

if isscalar(v)
    n = v;
else
    n = length(v);
end

if k>n
    error('Calling: randsubset(n,k) with n>=k')
end

a = ceil(rand(1,k).*(n-k+1:n));
for i=2:k
    ai = a(i);
    [trash loc] = histc(ai,a(1:i-1)); %#ok
    if loc==0
        if ai<a(1)
            a(2:i) = a(1:i-1);
            a(1) = ai;
        end
    elseif a(loc)<ai
        a(loc+2:i) = a(loc+1:i-1);
        a(loc+1) = ai;
    else
        a(i) = n-k+i;
    end
end % for-loop

if ~isscalar(v)
    a = v(a);
end

end % randsubset