algorithm - 是否有一种特定的算法来生成 n 个元素的所有组合，一次取 n-1

Question

我知道一般情况下的算法（例如，一次生成所有 n 个元素的组合），但我想知道是否有专门为 m=n-1 的情况设计的更快的算法。另外，如果存在这样的算法，任何人都可以指出 C/C++ 实现吗？

Answer 1

这很容易——使用一个简单的循环遍历所有元素。在这个循环中构造一个新集合，该集合由除一个（循环中的索引指向的那个）之外的所有元素组成。

注意：一些注释，以便您可以实现O(N)复杂性（C++例如，我将使用，但您可以使用任何其他具有类似矢量容器的语言）。

在C++：假设你有一个vector<int> a包含所有数字的：

vector<int> a;
... initialize a ....
vector<int> b(a.begin()+1, a.size()); // Now b will have all elements of a but the first one.

for (int i=0;i<a.size() - 1;++i) {
  b.push_back(a[i]);
  swap(b[i], b[b.size()-1]);
  b.pop_back();
}

使用上面的代码 b 将依次迭代所有组合。

Answer 2

如果一个集合有

• 2 个元素 {1,2} 子集将有 2^2 个元素 {},{1},{2},{1,2}
• 3 个元素 {1,2,3} 子集将有 2^3 个元素 {}、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{ 1,2,3}
• 4 个元素 {1,2,3,4} 子集将有 2^4 个元素 {}, {1},{2},{3},{4},{1,2},{1,3}, { 1,4}{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3 ,4},{1,2,3,4}

所以我认为上面的设置可以使用 2 个循环来实现

也在组合中

令 U 为具有 n 个元素的集合；我们想计算集合 U 中恰好有 j 个元素的不同子集的数量。这可以写成 N!/J! *（新泽西州）！

注意：可以删除空元素子集，公式变为 2^n-1

这是我的回答，如果这有帮助的话

• 如果 N=2 {1},{2}
• 对于 N=3 在 N=2 个元素 {1,3}{2,3} 的末尾添加 3 并混合 N=2 个元素 {1,2}
• 对于 N=4 在 N=3 个元素 {1,3,4}{2,3,4} {1,2,4} 的末尾添加 4 并混合 N=3 个元素 {1,2,3}

希望这可以帮助！！！