用于在任意长度集合中查找可变长度子集组合的算法

Question

我正在尝试制定一种方法，该方法将返回一个集合中子集的所有组合的列表。该方法调用看起来类似于 getSubsets(7, 3)，基于下图，我需要的返回输出的形式和顺序为:

123
124
125
126
127
134
135
136
137
145

...等等

下图准确显示了计数顺序应该如何进行。我一直在努力解决这个问题一天，找不到好的解决方案。 TIA。

Answer 1

获取给定子集之后的下一个子集:

1. 找到子集中其后继不在子集中的最大元素。
2. 删除该元素和子集中所有较大的元素。
3. 从后继元素开始，添加连续元素，直到子集的大小正确为止。

如果第 1 步失败，则您已经枚举了所有可能的子集。

在 C 中:

bool next_subset(int* subset, int n, int k) {
  // subset is a vector of k ints in the range [0, n)
  int i, j;
  for (i = k - 1, j = n - 1; subset[i] == j; --i, --j) {
    if (i == 0)
      return false; // No more subsets
  }
  for (j = subset[i] + 1; i < k ; ++i, ++j) {
    subset[i] = j;
  }
  return true;
}