Generowanie wszystkich kombinacji z powtarzaniem MATLAB

Question

Jak mogę stworzyć wszystkie k-combinations with repetitions danego zestawu (zwany również k-multicombinations lub multisubsets) przy użyciu MATLAB?

Jest podobny do produktu kartezjańskim, a dwa rzędy, które różnią się jedynie ich sortowania powinna być rozpatrywane jako takie same (na przykład wektory [1,1,2]=~=[1,2,1] które uważa się za ten sam), tak generujące iloczyn i następnie zastosowanie unique(sort(cartesianProduct,2),'rows') powinien dawać te same wyniki.

przykład: Połączenie nmultichoosek(1:n,k) powinien generować następującą macierz:

nmultichoosek(1:3,3) 
ans = 
    1  1  1 
    1  1  2 
    1  1  3 
    1  2  2 
    1  2  3 
    1  3  3 
    2  2  2 
    2  2  3 
    2  3  3 
    3  3  3 

Answer 1

Możemy użyć bijection wymienione w wikipedia article, która odwzorowuje kombinacji bez powtórzeń typu n+k-1 choose k do k -multicombinations wielkości n . Generujemy kombinacje bez powtórzeń i mapujemy je za pomocą bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1);. Powoduje to następującą funkcję:

function combs = nmultichoosek(values, k) 
%// Return number of multisubsets or actual multisubsets. 
if numel(values)==1 
    n = values; 
    combs = nchoosek(n+k-1,k); 
else 
    n = numel(values); 
    combs = bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1); 
    combs = reshape(values(combs),[],k); 
end 

Answer 2

Metoda Brute-Force: generuje wszystkie krotki, a następnie przechowuje tylko te, które są posortowane. Nie nadaje się do dużych wartości n lub k.

values = 1:3;        %// data 
k = 3;          %// data 
n = numel(values);       %// number of values 
combs = values(dec2base(0:n^k-1,n)-'0'+1); %// generate all tuples 
combs = combs(all(diff(combs.')>=0),:);  %'// keep only those that are sorted 

Answer 3

To jest chyba jeszcze bardziej brutalny sposób (pamięć intensywny) niż w poprzednich postach, ale schludny czytelny jedno-liner:

combs = unique(sort(nchoosek(repmat(values,1,k),k),2),'rows');