Generazione di tutte le combinazioni con ripetizione con MATLAB

Question

Come faccio a creare tutte k-combinations with repetitions di un dato insieme (chiamato anche k-multicombinations o multisubsets) con MATLAB?

Questo è simile al prodotto cartesiano, ma due righe che differiscono solo per il loro smistamento deve essere considerato lo stesso (ad esempio, i vettori [1,1,2]=~=[1,2,1] sono considerate essere la stessa), così generando il prodotto cartesiano e poi applicando unique(sort(cartesianProduct,2),'rows') dovrebbe produrre gli stessi risultati.

Esempio: La chiamata nmultichoosek(1:n,k) dovrebbe generare la seguente matrice:

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

possiamo usare il biiezione menzionato nella wikipedia article, che mappa combinazioni senza ripetizione di tipo n+k-1 choose k per k -multicombinations di dimensioni n . Generiamo le combinazioni senza ripetizione e le mappiamo usando bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1);. Ciò ha come risultato la seguente funzione:

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

Approccio forza bruta: genera tutte le tuple e quindi mantiene solo quelli ordinati. Non adatto a valori elevati di n o 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

Questo è probabilmente un metodo ancora più brutale (intensivo di memoria) di post precedenti, ma un ordine leggibile one-liner:

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