N选择K,KN,K-2N等递归内的递归

Question

我知道如何使用递归来生成所有可能的组合,即N选择K.但是如何创建K的所有可能的N/K组？N当然总是可以被K整除.为了澄清:例如,如果N是20而K是4,那么我想生成所有可能的五组四.如果说,N包含1,2,3 ... 20且K为4,那么一个这样的分组是{1,2,3,4},{5,6,7,8},{9,10 ,11,12},{13,14,15,16},{17,18,19,20}.假设N相对较小,因此递归是可行的

我觉得这是一个递归内递归问题,因为生成所有可能的单组四(又名N选K)需要递归,然后生成下一组四个变为N - 4选择K,并且接下来N - 8选择K等.但是我在实施这个问题时遇到了麻烦......有什么帮助吗？

Answer 1

std::next_permutation可能有帮助：

#include <algorithm>
#include <iostream>

int main()
{
    int v[] = {1, 2, 3, 4, 5, 6};

    do
    {
        std::cout << "{" << v[0] << "," << v[1] << "," << v[2] << "}, "
                  << "{" << v[3] << "," << v[4] << "," << v[5] << "}" << std::endl;

    } while (std::next_permutation(std::begin(v), std::end(v)));
    return 0;
}

哪个输出（6！解决方案）

{1,2,3}, {4,5,6}
{1,2,3}, {4,6,5}
...    
{6,5,4}, {3,1,2}
{6,5,4}, {3,2,1}

或者，如果组内的顺序并不重要，您可以尝试以下操作：

#include <algorithm>
#include <iostream>


int getNextIndex(const int (&v)[6], int start, int value)
{
    return std::find(std::begin(v) + start, std::end(v), value) - std::begin(v);
}

void print(const int (&v)[6])
{
    // Filter if you want that
    // `{1, 2, 3}, {4, 5, 6}` is equivalent to `{4, 5, 6}, {1, 2, 3}`
    if (getNextIndex(v, 0, 1) > getNextIndex(v, 0, 2)) return;
    //if (getNextIndex(v, 0, 2) > getNextIndex(v, 0, 3)) return; // And so on if you have more groups
    const char* sep[] = {", ", ", ", "}"};

    for (int i = 1; i != 3; ++i) {
        int index = -1;
        std::cout << "{";
        for (int j = 0; j != 3; ++j) {
            index = getNextIndex(v, index + 1, i);
            std::cout << 1 + index << sep[j];
        }
        std::cout << ", ";
    }
    std::cout << std::endl;
}

int main()
{
    int v[] = {1, 1, 1, 2, 2, 2};

    do
    {
        print(v);
    } while (std::next_permutation(std::begin(v), std::end(v)));
    return 0;
}

输出（10 个解决方案）：

{1, 2, 3}, {4, 5, 6},
{1, 2, 4}, {3, 5, 6},
{1, 2, 5}, {3, 4, 6},
{1, 2, 6}, {3, 4, 5},
{1, 3, 4}, {2, 5, 6},
{1, 3, 5}, {2, 4, 6},
{1, 3, 6}, {2, 4, 5},
{1, 4, 5}, {2, 3, 6},
{1, 4, 6}, {2, 3, 5},
{1, 5, 6}, {2, 3, 4},