返回可能重複的數組元素的所有獨特排列

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得到進一步改善。