0

nのパーティションを生成するためのこのアルゴリズムがあります：

def partitions(n):
    if n == 0:
        yield []
        return
    for p in partitions(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]

ただし、これを C++ に翻訳する方法さえわかりません。これは主に、yield 機能、部分文字列スライス、リスト連結などに相当する省略形がわからないためです。最も簡単な翻訳は何ですか?

4

1 に答える 1

0

便宜上、この投稿のBLUEPIXYの回答を少し編集しました。

#include <iostream>
#include <vector>

void save(std::vector<std::vector<int> > & dest, std::vector<int> const & v, int level){
    dest.push_back(std::vector<int>(v.begin(), v.begin() + level + 1));
}

void partition(int n, std::vector<int> & v, std::vector<std::vector<int> > & dest, int level = 0){
    int first; /* first is before last */
    if(0 == n){
        return;
    }
    v[level] = n;
    save(dest, v, level);

    first = (level == 0) ? 1 : v[level - 1];

    for(int i = first; i <= (n / 2); ++i){
        v[level] = i; /* replace last */
        partition(n - i, v, dest, level + 1);
    }
}

int main(int argc, char ** argv) {
    int N = 30;

    std::vector<int> vec(N);
    std::vector<std::vector<int> > partitions;
    // You could change N * N to minimize the number of relocations
    partitions.reserve(N * N);

    partition(N, vec, partitions);

    std::cout << "Partitions: " << partitions.size() << std::endl;
    for(std::vector<std::vector<int> >::iterator pit = partitions.begin(); pit != partitions.end(); ++pit) {
        std::cout << '[';
        for(std::vector<int>::iterator it = (*pit).begin(); it != (*pit).end(); ++it) {
            std::cout << *it << '\t';
        }
        std::cout << ']' << std::endl;
    }
    return 0;
}

ideoneでの出力

于 2013-03-18T16:39:54.443 に答える