返回可能重复的数组元素的所有独特排列

Question

比方说，我有长度N与M不同的对象（M < N）的阵列，使得一些这些对象的重复N_i ... N_M倍。我希望找到所有可能的独特的这种阵列的元素的配置（如，排列），而不必事先计算整个排列列表（包括时间和内存约束）。

当然，天真的解决办法是使用perms生成所有可能的排列，然后选择独特的：

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 

但这会产生所有N!排列，而不仅仅是N!/(N_1! * N_2! * ... * N_M!) 。对于N = 3，这不会影响很多的内存消耗和时间，但随着N增加和独特元素的数量减少，差异可能会很大。所以：

是否有一个（希望内置）的方式来列出包含非不同对象的数组的所有唯一排列，没有中间保持所有排列？

Answer 1

下面是代码在2014年提出通过Bruno Luong针对此问题：

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 

上面可通过用的Jan Simon's functions一个替换nchoosek得到进一步改善。