Die Erzeugung aller Kombinationen, die mindestens ein element einer gegebenen Menge in Matlab

Für eine brute-force-Lösung, die Sie erzeugen kann, die alle Ihre Kombinationen mit COMBNK dann die Funktionen verwenden, die JEDER und ISMEMBER zu finden, werden nur diejenigen Kombinationen enthalten, eine oder mehrere von einer Teilmenge von zahlen. Hier ist, wie können Sie das mit Ihrer obigen Beispiel:

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. Aber, ich habe verallgemeinert die Lösung, so dass es funktioniert für eine beliebige Anzahl von erforderlichen Elementen und für wiederholte Elemente in v. Die Funktion SUBCOMBNK finden Sie alle Kombinationen von k Werte aus einem Satz v dass mindestens einer der Werte im set 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

Testen kann man diese Funktion gegen die brute-force-Lösung oben, um zu sehen, dass es gibt dieselbe Ausgabe zurück:

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

Ich weiter getestet, diese Funktion gegen die brute-force-Lösung mit v = 1:15; und vSub = [3 5]; für Werte von N im Bereich von 2 bis 15. Die Kombinationen, die geschaffen wurden, waren identisch, aber SUBCOMBNK war deutlich schneller wie angezeigt durch den durchschnittlichen Laufzeiten (in MS) angezeigt unter:

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)