alle Kombinationen mit Wiederholung generieren MATLAB

Question

Verwendung Wie erstelle ich alle k-combinations with repetitions eines gegebenen Satzes mit MATLAB (auch k-multicombinations oder multisubsets genannt)?

Dies ist ähnlich zu dem Kartesischen Produkt, sondern zwei Reihen, die nur durch ihre Sortierung unterscheiden sollen das gleiche betrachtet werden (zum Beispiel der Vektoren [1,1,2]=~=[1,2,1] Betracht gezogen werden, um das gleiches sein), so dass das kartesische Produkt zu erzeugen und dann unique(sort(cartesianProduct,2),'rows') Anwendung ergeben sollte die gleichen Ergebnisse.

Beispiel: Der Aufruf nmultichoosek(1:n,k) die folgende Matrix erzeugen soll:

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

können wir die Bijektion im wikipedia article erwähnt verwendet werden, die Kombinationen abbildet ohne Wiederholung vom Typ n+k-1 choose k zu k -multicombinations der Größe n . Wir erzeugen die Kombinationen ohne Wiederholung und bilden sie unter Verwendung von bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1); ab. Dies führt zu folgender Funktion:

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

Brute-Force-Ansatz: Generiere alle Tupel und behalte dann nur diejenigen, die sortiert sind. Nicht geeignet für große Werte von n oder 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

Dies ist wahrscheinlich eine noch brutalere (speicherintensiv) Methode als frühere Beiträge, sondern ein ordentlich lesbar Einzeiler:

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