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

Question

我知道一般情况下的算法(例如生成所有组合n 个元素一次取 m 个)但我想知道是否有更快的一个专为 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 将依次迭代所有组合。