Генерация всех комбинаций, содержащих хотя бы один элемент из данного набора в Matlab - PullRequest
Новая
       10

Генерация всех комбинаций, содержащих хотя бы один элемент из данного набора в Matlab

9 голосов
/ 25 октября 2010

Я использую combnk для генерации списка комбинаций. Как я могу создать подмножество комбинаций, которое всегда включает в себя определенные значения. Например, для combnk(1:10, 2) мне нужны только комбинации, которые содержат 3 и / или 5. Есть ли быстрый способ сделать это?

Ответы [ 3 ]

6 голосов
/ 25 октября 2010

Ну, в вашем конкретном примере, выбрав два целых числа из набора {1, ..., 10} так, чтобы одно из выбранных целых чисел было 3 или 5, вы получите 9 + 9-1 = 17 известных комбинаций, поэтому просто перечислите их.

В общем, чтобы найти все n-select-k комбинаций из целых чисел {1, ..., n}, которые содержат целое число m, то же самое, что найти (n-1) -choose- (k) -1) комбинации из целых чисел {1, ..., m-1, m + 1, ..., n}.

В Matlab это будет 

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

(Этот код остается в силе, даже если m равен 1 или n.)

2 голосов
/ 25 октября 2010

Для решения методом грубой силы вы можете сгенерировать все свои комбинации с помощью COMBNK , а затем использовать функции ANY и ISMEMBER , чтобы найти только те комбинации, которые содержат однуили более подмножество чисел.Вот как вы можете сделать это, используя приведенный выше пример: 

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

РЕДАКТИРОВАТЬ:

Для более элегантного решения это выглядит как Стив и у меня была похожая идея.Однако я обобщил решение так, что оно работает как для произвольного числа требуемых элементов, так и для повторяющихся элементов в v.Функция SUBCOMBNK найдет все комбинации k значений, взятых из набора v, которые включают хотя бы одно из значений в наборе 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

. Вы можете проверить эту функцию поПриведенное выше решение о грубой силе показывает, что он возвращает тот же результат: 

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

Я дополнительно проверил эту функцию для решения с использованием грубой силы, используя v = 1:15; и vSub = [3 5]; для значений N в диапазоне от 2до 15. Созданные комбинации были идентичны, но SUBCOMBNK был значительно быстрее, как показано средним временем выполнения (в мсек), показанным ниже: 

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)
0 голосов
/ 26 октября 2010

Просто чтобы улучшить ответ Стива: в вашем случае (вам нужны все комбинации с 3 и / или 5) это будет

  • все комбинации k-1 / n-2 с 3 добавленными
  • все комбинации k-1 / n-2 с добавлением 5
  • все комбинации k-2 / n-2 с добавлением 3 и 5

Легко обобщается для любого другого случая этого типа.

...