从整数向量生成大小为 k 的下一个组合

Question

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

给定尺寸 k，我想生成 v 的所有 k 尺寸组合。

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 （如果可能的话) 和 return a bool 表明可以从 v.

中得到一些下一个组合

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

Answer 1

您标记了 C++，因此对您来说最简单的方法是使向量长度为 N，包含 K 个 1 和 (N-K) 个零，例如 {1,1,0,0,0} 并应用 std::next_permutation。

在每一步的位置显示-应该取什么数字进行组合。

例如排列{0,1,0,1,0}对应(1,3)组合

编辑

Jörg Arndt 的代码 Matters Computational book 使用现成的 K 长度数组（格式和可读性差）

 void first()
 {
     for (ulong k=0; k<k_; ++k)  x_[k] = k;
 }

 ulong next()
 // Return smallest position that changed, return k with last combination
 {
     if ( x_[0] == n_ - k_ )  // current combination is the last
     { first();  return k_; }

     ulong j = k_ - 1;
     // easy case:  highest element != highest possible value:
     if ( x_[j] < (n_-1) )  { ++x_[j];  return j; }

     // find highest falling edge:
     while ( 1 == (x_[j] - x_[j-1]) )  { --j; }

     // move lowest element of highest block up:
     ulong ret = j - 1;
     ulong z = ++x_[j-1];

     // ... and attach rest of block:
     while ( j < k_ )  { x_[j] = ++z;  ++j; }

     return  ret;
 }

Answer 2

involving std::next_permutation 就可读性而言更好。

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

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;
}

从整数向量生成大小为 k 的下一个组合

Generate next combination of size k from integer vector

c++

algorithm

math

combinations

combinatorics