Return all unique permutations of possibly-repeating array elements

Question

Let's say I have an array of length N with M different object (M < N) so that some of these objects repeat N_i ... N_M times. I'd like to find all possible unique dispositions (like, arrangements) of the elements of such arrays without computing the entire list of permutations beforehand (both for time and memory constraints).

Of course, the naive solution would be to use perms to generate all possible permutations, and then select the unique ones:

A = [1, 1, 2];

all_perms = perms(A)
    % all_perms =

    % 2     1     1
    % 2     1     1
    % 1     2     1
    % 1     1     2
    % 1     2     1
    % 1     1     2

unique_perms = unique(all_perms, 'rows')
    % unique_perms =

    % 1     1     2
    % 1     2     1
    % 2     1     1

but this will generate all N! permutations, instead of just the N! / (N_1! * N_2! * ... * N_M!). For N = 3, this doesn't affect much neither the memory consumption nor the timing, but as N increases and the number of unique elements decreases, the difference can be huge. So:

Is there a (hopefully built-in) way to list all the unique permutations of an array containing non distinct objects, without intermediately keeping all permutations?

Answer 1

Below is code suggested in 2014 by Bruno Luong for this problem:

function p = uperm(a)
[u, ~, J] = unique(a);
p = u(up(J, length(a)));
end % uperm

function p = up(J, n)
ktab = histc(J,1:max(J));
l = n;
p = zeros(1, n);
s = 1;
for i=1:length(ktab)
    k = ktab(i);
    c = nchoosek(1:l, k);
    m = size(c,1);
    [t, ~] = find(~p.');
    t = reshape(t, [], s);
    c = t(c,:)';
    s = s*m;
    r = repmat((1:s)',[1 k]);
    q = accumarray([r(:) c(:)], i, [s n]);
    p = repmat(p, [m 1]) + q;
    l = l - k;
end
end

The above can be further improved by replacing nchoosek with one of Jan Simon's functions.