使用递归对数字进行每个分区

Question

在做一些回溯练习时，卡在了这里：

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 将是：

我在网上搜索了解决方案，找到了this，但不太正确，我不知道如何完善它。首先它不是按字典顺序排列的，并且不包括实际数字。

所以对于 5 它输出：

这是我的代码，我尝试更正它，它更好，但仍然不完全是示例的方式..

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

所以，现在输出是：

所以，2 2 1 和 3 2 放错了地方..而且“n”数越大，越乱..

有人可以帮忙吗？

Answer 1

如果您只是想要答案...这里是我几年前从 Python 翻译成 C# 的一些代码，并且刚刚翻译成 C++ 来获得这个答案。

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

Python 代码来自这里，Generator for integer partitions (Python recipe)，作者在评论中做了一些解释。

在我的 C# 代码中，我能够保留 Python 版本中使用的 generator/yield 习语，但恐怕我目前还不知道如何使用 C++ 协程，所以我已经将其移至标准函数实现，这将降低效率，因为它需要大量复制。

Answer 2

当你进行更多的编程练习时，你将学会如何让事情变得简单：

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

使用递归对数字进行每个分区

Every partition of a number using recursion

c++

recursion

backtracking