Generieren aller Kombinationen, die mindestens ein Element einer gegebenen Menge in Matlab enthalten

Question

Ich verwende combnk, um eine Liste von Kombinationen zu generieren. Wie kann ich eine Teilmenge von Kombinationen generieren, die immer bestimmte Werte enthält. Zum Beispiel, für combnk(1:10, 2) Ich brauche nur Kombinationen, die 3 und/oder 5 enthalten. Gibt es einen schnellen Weg, dies zu tun?

Answer 1

Nun, in Ihrem speziellen Beispiel, zwei Integer aus der Menge {1, ..., 10} so wählen, dass eine der gewählten ganzen Zahlen 3 oder 5 ergibt 9 + 9-1 = 17 bekannten Kombinationen, so Sie kann sie nur aufzählen.

Um alle n-choose-k-Kombinationen aus Ganzzahlen {1, ..., n} zu finden, die die ganze Zahl m enthalten, ist das das Gleiche wie das Finden der (n-1) -Auswahl- (k-1) Kombinationen aus ganzen Zahlen {1, ..., m-1, m + 1, ..., n}.

in Matlab, das wäre

combnk([1:m-1 m+1:n], k-1) 

(Dieser Code ist immer noch gültig, auch wenn m 1 oder n.)

Answer 2

Für eine Brute-Force-Lösung, können Sie alle Ihre Kombinationen mit COMBNK erzeugen Verwenden Sie dann die Funktionen ANY und ISMEMBER, um nur die Kombinationen zu finden, die eine oder mehrere Teilmengen enthalten. Hier ist, wie Sie es tun können Ihr obiges Beispiel mit:

v = 1:10;   %# Set of elements 
vSub = [3 5];  %# Required elements (i.e. at least one must appear in the 
        %# combinations that are generated) 
c = combnk(v,2);  %# Find pairwise combinations of the numbers 1 through 10 
rowIndex = any(ismember(c,vSub),2); %# Get row indices where 3 and/or 5 appear 
c = c(rowIndex,:); %# Keep only combinations with 3 and/or 5 

---

EDIT:

Für eine elegantere Lösung, es sieht aus wie Steve und ich hatte eine ähnliche Idee. Allerdings habe ich die Lösung so verallgemeinert, dass sie sowohl für eine beliebige Anzahl erforderlicher Elemente als auch für wiederholte Elemente in v funktioniert. Die Funktion SUBCOMBNK werden alle Kombinationen von k Werte aus einem Satz v genommen finden, die zumindest einer der Werte in der Menge enthalten vSub:

function c = subcombnk(v,vSub,k) 
%#SUBCOMBNK All combinations of the N elements in V taken K at a time and 
%# with one or more of the elements in VSUB as members. 

    %# Error-checking (minimal): 

    if ~all(ismember(vSub,v)) 
    error('The values in vSub must also be in v.'); 
    end 

    %# Initializations: 

    index = ismember(v,vSub); %# Index of elements in v that are in vSub 
    vSub = v(index);   %# Get elements in v that are in vSub 
    v = v(~index);    %# Get elements in v that are not in vSub 
    nSubset = numel(vSub);  %# Number of elements in vSub 
    nElements = numel(v);  %# Number of elements in v 
    c = [];     %# Initialize combinations to empty 

    %# Find combinations: 

    for kSub = max(1,k-nElements):min(k,nSubset) 
    M1 = combnk(vSub,kSub); 
    if kSub == k 
     c = [c; M1]; 
    else 
     M2 = combnk(v,k-kSub); 
     c = [c; kron(M1,ones(size(M2,1),1)) repmat(M2,size(M1,1),1)]; 
    end 
    end 

end 

Sie diese Funktion gegen die Brute-Force-Lösung oben testen, kann man erkennen, es gibt denselben Ausgang:

cSub = subcombnk(v,vSub,2); 
setxor(c,sort(cSub,2),'rows') %# Returns an empty matrix if c and cSub 
           %# contain exactly the same rows 

I weiter diese Funktion gegen die Brute-Force-Lösung v = 1:15;vSub = [3 5]; und für Werte von N von 2 bis 15. die Kombinationen waren identisch erstellt Bereich unter Verwendung getestet, aber SUBCOMBNK war deutlich schneller als angezeigt unten durch den mittleren Laufzeiten (in ms) gezeigt:

N | brute force | SUBCOMBNK 
---+-------------+---------- 
2 |  1.49 | 0.98 
3 |  4.91 | 1.17 
4 | 17.67 | 4.67 
5 | 22.35 | 8.67 
6 | 30.71 | 11.71 
7 | 36.80 | 14.46 
8 | 35.41 | 16.69 
9 | 31.85 | 16.71 
10 | 25.03 | 12.56 
11 | 19.62 | 9.46 
12 | 16.14 | 7.30 
13 | 14.32 | 4.32 
14 |  0.14 | 0.59* #This could probably be sped up by checking for 
15 |  0.11 | 0.33* #simplified cases (i.e. all elements in v used) 

Answer 3

Gerade Steve Antwort zu verbessern: in Ihrem Fall (alle denkbaren Kombinationen wollen mit 3 und/oder 5) wird es sein

• alle k-1/n-2-Kombinationen mit 3 hinzugefügt
• alle k-1/n-2-Kombinationen mit 5 hinzugefügt
• alle k-2/n-2-Kombinationen mit 3 und 5 hinzugefügt

Leicht generalisiert für jeden anderen Fall dieses Typs.