按顺序生成数字分区的不同方法

Question

我的算法教科书中有一个练习要求我按顺序生成 partitions of a number。我已经解决了，但是在用传统方法解决这个问题的时候，我想出了一个解决这个问题的新想法。

有传统做法：

#include <iostream>

#define MAX_PARTITIONS 100

int count = 1;

void printSolution(int* solution, int size)
{
    std::cout << count << "| ";
    count++;
    for(int i = 0; i < size; i++)
    {
        std::cout << solution[i] << " ";
    }
    std::cout << std::endl;
}

void generatePartitions(int* solution, int number, int sum, int partitions)
{
    if(sum == number)
    {
        printSolution(solution, partitions);
        return;
    }

    if(partitions > 1)
    {
        solution[partitions] = solution[partitions - 1];
    }
    else
    {
        solution[partitions] = 0;
    }

    while(solution[partitions] + sum < number)
    {
        solution[partitions]++;
        sum += solution[partitions];
        generatePartitions(solution, number, sum, partitions + 1);
        sum -= solution[partitions];
    }
}

int main(int argc, char const *argv[])
{
    int solution[MAX_PARTITIONS];

    generatePartitions(solution, 4, 0, 0);

    return 0;
}

基本上，当分区数大于1时（存在前一个分区）我将前一个分区的值分配给当前分区，否则我将0分配给它.

有新方法：

#include <iostream>

#define MAX_PARTITIONS 100

int count = 1;

void printSolution(int* solution, int size)
{
    std::cout << count << "| ";
    count++;
    for(int i = 0; i < size; i++)
    {
        std::cout << solution[i] << " ";
    }
    std::cout << std::endl;
}

void generatePartitions(int* solution, int number, int sum, int partitions, 
    int start)
{
    if(sum == number)
    {
        printSolution(solution, partitions);
        return;
    }

    solution[partitions] = start;

    while(solution[partitions] + sum < number)
    {
        solution[partitions]++;
        sum += solution[partitions];
        generatePartitions(solution, number, sum, partitions + 1, 
            solution[partitions]);
        sum -= solution[partitions];
    }
}

int main(int argc, char const *argv[])
{
    int solution[MAX_PARTITIONS];

    generatePartitions(solution, 4, 0, 0, 0);

    return 0;
}

如您所见，函数 generatePartitions 现在有一个新参数 start。最初，start 的值是 0，并且在每次递归调用时 start 取当前 solution[partitions] 的值。所以它应该和传统方法一样工作。

但事实并非如此，这些程序的输出是完全不同的。我不知道出了什么问题。我做错了什么？

Answer 1

您在递归时忘记移动 solution 数组的索引。

generatePartitions(solution, number, sum, partitions + 1, 
            solution[partitions]);

变成：

generatePartitions(solution, number, sum, partitions + 1, 
            solution[partitions-1]);

科里鲁 link: http://coliru.stacked-crooked.com/a/83b0418e1b1c9bc1

另外，我建议使用某种形式的 std::pair<int,int> 和某种二叉树来为你做这件事——对我来说，从上到下更有意义，因为我们正在尝试从技术上将一个数字划分或划分为更小的数字；该算法可能有点复杂，但也可以在完成后显示一棵树。

按顺序生成数字分区的不同方法

Different ways of generating the partitions of a number in order

c++

algorithm

number-theory