Different ways of generating the partitions of a number in order

Question

I have an exercise in my algorithms text book that asks me to generate the partitions of a number in order. I have solved it, but while solving the exercise the traditional way I came up with a new idea of solving that problem.

There is the traditional approach:

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

Basically, when the number of partitions is bigger than 1 (there exists a previous partition) I assign to the current partition the value of the previous one, otherwise I assign 0 to it.

There is the new approach:

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

As you can see, the function generatePartitions takes now a new parameter, start. Initially, the value of start is 0, and at each recursive call start takes the value of the current solution[partitions]. So it should work in the same way as the traditional method.

But it doesn't, the output of these programs is completely different. I can't figure out what is wrong. What am I doing wrong?

Answer 1

You forgot to move the index of the solution array when you recurse.

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

becomes:

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

Coliru link: http://coliru.stacked-crooked.com/a/83b0418e1b1c9bc1

Also, I'd propose using some form of std::pair<int,int> and a binary tree of some sort to do this for you--for me, it makes more sense to go from the top down, as we are trying to technically divide or partition a number into smaller ones; the algorithm might be a bit complex, but it might be possible to show a tree when you're done with it as well.