c++ - 从整数 vector 生成大小为 k 的下一个组合

Question

假设我有一个整数 vector v = {0, 1,..., N-1}，大小为 N。

给定大小 k，我想生成所有 k 大小的 v 组合。

for example: k = 2, N = 10
    {0,1}, {0,2}, ..., {0,9}, {1,2}, ..., {8,9}

但我想一个一个地做，使用一个叫做NextCombination的方法:

bool NextCombination(vector<int>& v, int k, int N){
    if( is not the last combination){
        turn v into it's next combination
        return true;
    }
    return false;
}

这意味着，给定 v 的当前状态、组合的大小 k 和元素的总数，我想更改 v (如果可能)并返回一个 bool，表示可以从 v 中获取下一个组合。

如果没有一些无聊的递归，我无法弄清楚如何做到这一点，并且由于这只是我正在做的事情的小问题，我想找出一些聪明/小的解决方案。

Answer 1

就可读性而言，包含 MBo's answer 的 std::next_permutation 更好。

但是，这需要制作一个由 1 和 0 组成的 N 大小的 vector ，如果你真的想节省内存，你可以不用它。以下解决方案本质上就地执行相同的操作。

bool NextCombination(vector<int>& v, int k, int N) {
  // We want to find the index of the least significant element
  // in v that can be increased.  Let's call that index 'pivot'.
  int pivot = k - 1;
  while (pivot >= 0 && v[pivot] == N - k + pivot)
    --pivot;

  // pivot will be -1 iff v == {N - k, N - k + 1, ..., N - 1},
  // in which case, there is no next combination.
  if (pivot == -1)
    return false;

  ++v[pivot];
  for (int i = pivot + 1; i < k; ++i)
    v[i] = v[pivot] + i - pivot;
  return true;
}