Every partition of a number using recursion-CodePudding

While doing some backtracking exercises, got stuck here:

Write a recursive algorithm that generates all partitions of a given n numbers. Of the partitions that differ only in the order of the members, we need to list only one, the last from a lexicographic point of view. Write the solutions lexicographically in ascending order. 1 <= n <= 100

n = 5 would be:

I searched over the web for solutions and found this, but it's not quite right and I don't know how to perfect it. First of all it's not in lexicographical order, and doesn't include the actual number.

So for 5 it outputs:

Here is my code, where I tried to correct it, it's better, but still not exactly the way the example is..

#include <iostream>
#include <vector>
using namespace std;

void print(const vector<vector<int>>& output)
{
  for(int i = 0; i < output.size();   i){
    for(int j = output[i].size()-1; j >= 0; --j){
      cout << output[i][j] << " "; 
    }
    cout << endl;
  }
}

void iteration(int n, int current_sum, int start, vector<vector<int>>& output, vector<int>& result)
{
    if (n == current_sum) {
        output.push_back(result);
    }

    for (int i = start; i < n; i  ) {
        int temp = current_sum   i;
        if (temp <= n) {
            result.push_back(i);
            iteration(n, temp, i, output, result);
            result.pop_back();
        }
        else {
            return ;
        }
    }
}

void decompose(int n) 
{
    vector<vector<int>> output;
    vector<int> result;

    iteration(n, 0, 1, output, result);

    print(output);
    cout << n << endl;

    return ;
}

int main() 
{
    int n = 5;
    decompose(n);

    return 0;
}

So, now the output is:

So, the 2 2 1 and 3 2 is in the wrong place.. And the bigger the "n" number is, the bigger the mess..

Can someone help?

CodePudding user response：

If you just want the answer ... here is some code that I translated from Python to C# a few years ago and just translated to C for this answer.

#include <iostream>
#include <vector>

std::vector<int> join(int val, const std::vector<int>& vec) {
    std::vector<int> joined;
    joined.reserve(vec.size()   1);
    joined.push_back(val);
    std::copy(vec.begin(), vec.end(), std::back_inserter(joined));
    return joined;
}

std::vector<int> tail(const std::vector<int>& v) {
    std::vector<int> t(v.size() - 1);
    std::copy(std::next(v.begin()), v.end(), t.begin());
    return t;
}

std::vector<std::vector<int>> partitions(int n) {
    if (n == 0) {
        return { {} };
    }
    auto partitions_n_minus_1 = partitions(n - 1);
    std::vector<std::vector<int>> partitions_n;

    for (const auto& p: partitions_n_minus_1) {
        partitions_n.push_back( join({ 1 }, p) );
        if (!p.empty() && (p.size() < 2 || p[1] > p[0])) {
            partitions_n.push_back(join({ p[0]   1 }, tail(p)));
        }
    }
    return partitions_n;
}

int main()
{
    auto partions = partitions( 6 );
    for (const auto& p : partions) {
        for (int i : p) {
            std::cout << i << " ";
        }
        std::cout << "\n";
    }

    return 0;
}

The Python code this comes from is here, Generator for integer partitions (Python recipe), with some explanation by the author in comments.

In my C# code I was able to retain the generator/yield idiom used in the Python version but I'm afraid I currently do not know how to use C coroutines yet so I've moved it to a standard function implementation which will be less efficient as it requires a lot of copying.

CodePudding user response：

When you get more practice programming, you'll learn how to keep things simple:

#include <iostream>
#include <vector>

void decompose(int n, std::vector<int> prefix = {})
{
  if (n == 0) {
    for (int a : prefix) { std::cout << a << ' '; }
    std::cout << std::endl;
  }
  else {
    int max = prefix.size() ? std::min(prefix.back(), n) : n;
    prefix.push_back(1);
    for (int i = 1; i <= max; i  ) {
      prefix.back() = i;
      decompose(n - i, prefix);
    }
  }
}

int main()
{
  decompose(5);
}