Générer toutes les combinaisons contenant au moins un élément d'un ensemble donné en Matlab

Pour une attaque par force brute solution, vous pouvez générer tous vos combinaisons avec COMBNK utiliser les fonctions de la TOUT et ISMEMBER afin de trouver les combinaisons qui contiennent un ou plus d'un sous-ensemble de nombres. Voici comment vous pouvez le faire en utilisant votre exemple ci-dessus:

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:

Pour une solution plus élégante, on dirait Steve et j'ai eu une idée similaire. Cependant, j'ai généralisé la solution de sorte qu'il fonctionne pour un nombre arbitraire d'éléments requis, et pour les éléments répétés dans v. La fonction SUBCOMBNK trouverez toutes les combinaisons de k valeurs prises à partir d'un ensemble v qui comprennent au moins l'une des valeurs dans l'ensemble 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

Vous pouvez tester cette fonction à l'encontre de la force brute de la solution ci-dessus pour voir qu'il retourne le même résultat:

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

J'ai encore testé cette fonction, contre la force brute de la solution à l'aide de v = 1:15; et vSub = [3 5]; pour les valeurs de N allant de 2 à 15. Les combinaisons créées sont identiques, mais SUBCOMBNK a été nettement plus rapide, comme indiqué par la moyenne des temps d'exécution (ms) de l'affiche ci-dessous:

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)

OriginalL'auteur gnovice