Fast unique random permutations

Fast random sample (without replacement) from unique permutations of an integer vector

%uniqperms: unique permutations of an input vector x
% Usage: nPerms = uniqperms(x)
% [nPerms pInds] = uniqperms(x)
% [nPerms pInds Perms] = uniqperms(x)
% [nPerms pInds] = uniqperms(x, k)
% [nPerms pInds Perms] = uniqperms(x, k)
% [nPerms pInds Perms] = uniqperms(x,k,first)
%
% Determines number of unique permutations (nPerms) for vector x.
% Optionally, all permutations indices (pInds) are returned. If requested,
% permutations of the original input (Perms) are also returned.
%
% If k < nPerms, a random (but still unique) subset of k of permutations is
% returned.
%
% If k >= nPerms, a random (but still unique) subset of nPerms of permutations is
% returned. The original/identity permutation will be the first of these.
%
% Row or column vector x results in Perms being a [k length(x)] array,
% consistent with MATLAB's built-in perms. pInds is also [k length(x)].
%
% If first = true then the original/identity permutation will be the first of these.
% (first = false ... opposite case)
%
% Examples:
% uniqperms(1:7), factorial(7) % verify counts in simple case,
% uniqperms([1 1 2]), factorial(3)/prod(factorial([2 1])) % verify counts in nonunique case,
% [nPerms,pInds Perms] = uniqperms([1 1 1 2 2], 3))
% nPerms =
% 10
%
% pInds =
%
% 1 3 2 5 4
% 1 3 5 2 4
% 1 3 5 4 2
%
% Perms =
%
% 1 1 1 2 2
% 1 1 2 1 2
% 1 1 2 2 1
%
% Copyright 2018 Michal Kvasnicka
% UJV Rez, a.s.