在 Matlab 中生成包含给定集合中至少一个元素的所有组合

Question

我使用 combnk 生成组合列表。如何生成始终包含特定值的组合子集。例如，对于 combnk(1:10, 2) 我只需要包含 3 和/或 5 的组合。有没有快速的方法来做到这一点？

Answer 1

好吧，在您的具体示例中，从集合 {1, ..., 10} 中选择两个整数，其中所选整数之一为 3 或 5，会产生 9+9-1 = 17 个已知组合，因此您可以枚举它们。

一般来说，从包含整数 m 的整数 {1, ..., n} 中查找所有 n-choose-k 组合，这与查找 (n-1)-choose-(k-1) 相同整数 {1, ..., m-1, m+1, ..., n} 的组合。

在 matlab 中，这将是

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

（即使 m 为 1 或 n，此代码仍然有效。）

Answer 2

对于强力解决方案，您可以使用 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 将查找取自集合 v 的所有 k 值的组合，其中至少包含集合 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]; 对于从 2 到 15 的 N 值。创建的组合是相同的，但 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)

Answer 3

只是为了改进史蒂夫的答案：在你的情况下（你想要所有与 3 和/或 5 的组合），它将是

• 所有 k-1/n-2 组合，其中 3 添加了
• 所有 k-1/n-添加了 5 个的 2 个组合
• 添加了 3 个和 5 个的所有 k-2/n-2 组合

可以轻松推广到该类型的任何其他情况。