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

Question

可以说我有整数向量V = {0,1，...，N-1}的大小N.

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

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

但我想这样做，一个接一个，使用一个名为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和e的总数lement，我想改变v（如果可能的话），并返回一个布尔值，表明它有可能从v得到一些下一个组合

我想不出如何做到这一点，没有一些无聊的递归，这只是我正在做的一个小问题，我想找出一些聪明/小解决方案。

Answer 1

MBo's answer涉及std::next_permutation更好至于可读性关注

编辑

代码。

然而，这需要使得1和0，你可以不用，如果你真的想节省内存做的N大小的矢量。 以下解决方案在本质上做同样的事情。

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

Answer 2

您标记了C++，所以最简单的方法 - 使向量长度为​​N，包含K个和（N-K）个零像{1,1,0,0,0}和应用std::next_permutation。

在那些每一步的位置展示区 - 应该采取什么样的号码组合。

例如，置换{0,1,0,1,0}对应于(1,3)组合。从约克·阿恩特的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; 
}