2024-05-06 11:34:26 发布
网友
我有一个生成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:]
为了您的方便,我在this的帖子上对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上的输出
为了您的方便,我在this的帖子上对BLUEPIXY的答案做了一点编辑。你知道吗
ideone上的输出
相关问题 更多 >
编程相关推荐