N选择K、K-N、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，依此类推。但是我在实现this...any帮助时遇到了问题吗？

Answer 1

术语:您想要的是将一组N个元素分成每个大小为K的部分的所有。有n!/((k!)^(n/k) (n/k)!)这样的分区(参见answer on math.SE)。

为了避免过度生成，让我们为每个分区确定一个“规范形式”：假设它是以递增的顺序编写每个部分，然后以其最小元素的递增顺序编写这些部分本身。

现在，您可以将分区的生成可视化为将编号为1到N的球一个接一个地放入N/K个桶中的过程。然后自动满足每个bin (部分)必须按递增顺序排列的约束(当然，您应该按照插入元素的顺序“读取”每个bin )，并且如果我们确保在填充下一个空bin之前不跳过空bin，则满足对part的约束。

现在将其转换为代码。让我们将分区(或一堆桶)建模为向量的向量。

#include <iostream>
#include <vector>
#include <cassert>

std::vector< std::vector<int> > partition;
int N, K;
int num_partitions_found = 0;

void OutputPartition();

一般而言，当以递归方式生成结构(或编写任何递归算法)时，您的递归函数会被赋予一个特定的“状态”，并尝试以每种增量方式扩展该状态。在不同的选项之间，只要确保将状态恢复到给定的状态即可。

所以让我们写一个递归函数，它接受一个状态，在这个状态下，直到n-1的球都被放在了n中，并通过把球放在所有可能的地方来扩展这个状态。

void GeneratePartitions(int n) {
  // When we've placed all N elements, output and stop.
  if (n == N + 1) {
    OutputPartition();
    return;
  }
  // Place ball n into each allowed bin.
  for (int i = 0; i < N / K; ++i) {
    // Cannot place into a full bin
    if (partition[i].size() == K) continue;
    // Cannot skip an empty bin
    if (i > 0 && partition[i-1].empty()) break;
    // Place the ball here: extending the state
    partition[i].push_back(n);
    // How to extend the new state is left to the recursive call
    GeneratePartitions(n + 1);
    // Make sure you restore state after each recursive call!
    partition[i].pop_back();
  }
}

这是递归的核心。程序的其余部分都是脚手架。

void OutputPartition() {
  assert(partition.size() == N/K);
  ++num_partitions_found;
  for (int i = 0; i < N/K; ++i) {
    assert(partition[i].size() == K);
    std::cout << "{";
    for (int j = 0; j < K; ++j) {
      std::cout << partition[i][j] << (j == K - 1 ? "}" : ", ");
    }
    if (i < N/K - 1) std::cout << ", ";
  }
  std::cout << std::endl;
}

int main() {
  std::cin >> N >> K;
  assert(N % K == 0);
  partition.resize(N / K);
  GeneratePartitions(1);
  std::cout << num_partitions_found << " found" << std::endl;
}

注意:这篇文章是一个literate program：如果你把代码片段放在一起，你就有了一个有效的工作程序。

或者，如果您想尝试该程序(请参阅它的运行速度等)，另一个版本是here on github：它不使用全局变量，使用普通的数组(更快)作为分区，并且只打印所有找到的分区(编辑代码以更改它)。

回到你的问题，我们看到，通过仔细考虑这个问题一段时间，你可以避免不同类型的递归。即使您这样做了，编写递归程序的一般方法仍然有效:编写一个接受状态的递归函数，以所有可能的方式将其扩展一步(将这些状态的进一步扩展传递给递归调用)，然后清除到其原始状态。(有时，当状态很小时，您不必做任何清理工作--您可以将状态与函数调用一起传递--但有时由递归调用共享状态会更干净。)

Answer 2

该解决方案在两个级别使用递归：

查找组合C(n，k)：k步

• 查找n/k个C(n，k)的序列: n/k步

为了避免以不同的顺序重复分组:每个分组中的第一个元素必须小于或等于位置。结果是第一组总是以1开头，举个例子。

一些结果：

• 3种组合，适用于4-2
• 10种组合，适用于6-3
• 15种组合，适用于6-2

我想知道计算公式，以便进一步验证结果。

#include <vector>
#include <set>
#include <iostream>
#include <cassert>
#include <fstream>

namespace lan
{

struct Solution
{
    virtual bool Next(const std::vector<unsigned>&) = 0;
};
void SetCombination(const size_t, const size_t, Solution*);

struct ToPrint: public Solution
{
    ToPrint(): m_cnt(0) {};

    void Print(const std::vector<unsigned>& solution, std::ostream& out, size_t grouped = 0)
    {
        assert(grouped <= solution.size());
        if (grouped)
            out<<"{";
        for (size_t i = 0; i < solution.size(); ++i)
        {
            if (i)
            {
                if (grouped && !(i%grouped))
                    out<<"} {";
                else
                    out<<" ";
            }
            out<<solution[i];
        }
        if (grouped)
            out<<"}";
        out<<std::endl;
    }

    bool Next(const std::vector<unsigned>& solution)
    {
        Print(solution, std::cout);
        ++m_cnt;
        return true;
    }

    size_t Count() const {return m_cnt;};

protected:
    size_t m_cnt;
};

struct GroupOf: public ToPrint
{
    typedef ToPrint Super;

    GroupOf(int length, int group, bool print): m_length(length), m_group(group), m_print(print)
    {
        assert(!(length%group));
        //m_out.open("out.txt");
        //assert(m_out);
    }

    bool Next(const std::vector<unsigned>& partial)
    {
        assert(m_group == partial.size());
        size_t i;
        for (i = 0; i < m_group-1; ++i)
            assert(partial[i] < partial[i+1]);

        //  first element in each partial solution must be <= position (to avoid groups recombination)

        if (partial[0] > 0)
            return false;

        //  add the next group to the solution

        assert(m_sum <= m_length-m_group);
        size_t j, k; 
        for (i = j = k = 0; (i < m_length) && (j < m_group); ++i)
        {
            if (!m_solution[i] && (k++ == partial[j]))
            {
                j++;
                m_solution[i] = j + m_sum;
            }
        }
        assert(j == m_group);

        //  process a solution or go after the next group, recursively

        m_sum += m_group;
        if (m_sum == m_length)
        {
            std::vector<unsigned> print;
            Translate(m_solution, print); 
            if (m_print)
                //Print(print, m_out, m_group);
                Print(print, std::cout, m_group);
            assert(Validate(print));
            ++m_cnt;
        }
        else 
            SetCombination(m_length-m_sum, m_group, this);

        //  restore "stack" of recursive calls

        m_sum -= m_group;
        for (i = 0; i < m_length; ++i)
            if (m_solution[i] > m_sum)
                m_solution[i] = 0;

        return true;
    };

    void Start()
    {   
        m_sum = 0;
        m_solution.assign(m_length, 0);

        SetCombination(m_length, m_group, this);
    };

protected:
    //  transform positions to "real" solution
    static 
    void Translate(const std::vector<unsigned>& a, std::vector<unsigned>& b)
    {
        b.resize(a.size());
        for (size_t i = 0; i < a.size(); ++i)
        {
            assert(a[i]);
            b[a[i]-1] = 1+i;
        }
    }

#ifdef _DEBUG
    static 
    bool Validate(const std::vector<unsigned>& a)
    {
        std::set<unsigned> elements; 
        for (size_t i = 0; i < a.size(); ++i)
            elements.insert(a[i]);
        if (elements.size() != a.size())
            return false;

        return true;
    }
#else
    static 
    bool Validate(const std::vector<unsigned>&)
    {
        return true;
    }
#endif 

private:
    GroupOf& operator= (const GroupOf&);

protected:
    const size_t m_length;
    const size_t m_group;
    const bool m_print;

    size_t m_sum;
    std::vector<unsigned> m_solution;
    //std::ofstream m_out;
};

//  get a 'length' by 'group' combination; since it's strictly ordered ( = ... the order doesn't matter), the first index is "next"
bool SetCombination(const size_t length, const size_t group, size_t next, std::vector<unsigned>& solution, Solution* cbk)
{
    assert(length);
    assert(cbk);
    assert(group <= length);
    assert(next < length);

    for (size_t i = next; i < length; ++i)
    {
        solution.push_back(i);
        next = i+1;

        if (solution.size() == group)
        {
            if (!cbk->Next(solution))
                return false;
        }
        else if (next != length)
        {
            if (!SetCombination(length, group, next, solution, cbk))
                return false; //break;
        }

        solution.pop_back();
    }

    return true;
}

void SetCombination(const size_t length, const size_t group, Solution* cbk)
{
    std::vector<unsigned> solution;
    (void)SetCombination(length, group, 0, solution, cbk);
}

size_t Test(size_t total, size_t grouped, bool print = false)
{
    GroupOf test(total, grouped, print);
    test.Start();

    return test.Count();
}

}

到目前为止的所有结果：

assert(3 == lan::Test(4, 2));
assert(10 == lan::Test(6, 3));
assert(15 == lan::Test(6, 2));
assert(126 == lan::Test(10, 5));
assert(280 == lan::Test(9, 3));
assert(945 == lan::Test(10, 2));
if (0)
{
    assert(1716 == lan::Test(14, 7));
    assert(5775 == lan::Test(12, 4));
    assert(126126 == lan::Test(15, 5)); //  1s, Release
}

Answer 3

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