生成{0,1,2，... n

本文介绍了生成{0,1,2，... n-1}的所有大小k个子集，的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想生成所有基数 k {0,1,2，...，n-1}的子集在C ++。在Haskell中，我会：

sets 0 n = [[]] 设置kn = [i：s | i < - [0..n-1]，s < - set（k-1）i]

$ b b

或在Python中：

def sets（k，n）： if k == 0： return [（）] return（（i，）+ s for（in）（n）for s in sets（k-1，i））

例如，（为了清楚起见，换行符）

ghci>设置2 8 [[1,0]， [2,0]，[2,1]， [3,0]，[3,1]，[3,2 ]， [4,0]，[4,1]，[4,2]，[4,3]， [5,0]，[5,1] ]，[5,3]，[5,4]， [6,0]，[6,1]，[6,2]，[6,3]，[6,4] ，5]， [7,0]，[7,1]，[7,2]，[7,3]，[7,4]，[7,5]，[7,6]

这样做的C ++方式是什么？请注意，我不是要求如何来解决这个问题。我想知道什么数据类型被C ++程序员认为是正常的。

（参考，我熟悉C ++， 。

解决方案

这里是一个朴素的递归方法，它实现了古典的组合身份：

binom（n + 1，k + 1）= binom（n，k + 1）+ binom b

#include< set> typedef std :: set< int> intset; std :: set< intset>子集（std :: size_t k，intset s） { if（k == 0 || s.empty（）|| s.size（）< k）{return {{} ; } if（s.size（）== k）{return {s}; } auto x = * s.begin（）; s.erase（s.begin（））; std :: set< intset>结果; for（auto& t：subsets（k - 1，s）） { auto r = std :: move（t）; r.insert（x）; result.insert（std :: move（r））; } for（auto& t：subsets（k，s）） { results.insert（std :: move（t））; } 返回结果; }

用法：

auto ss = subsets（3，{0，1，2，3，4}）;

完成示例：

#include< iostream> #include< string> #include< prettyprint.hpp> int main（int argc，char * argv []） { if（argc！= 3）return 1; auto k = std :: stoul（argv [1]）; auto n = std :: stoul（argv [2]）; intset s; for（auto i = 0U; i！= n; ++ i）s.insert（i）; std :: cout<<子集（k，s） std :: endl; }

I want to generate all cardinality k subsets of {0, 1, 2, ..., n-1} in C++. In Haskell, I would do:

sets 0 n = [[]] sets k n = [i:s | i <- [0..n-1], s <- sets (k-1) i]

Or in Python:

def sets(k, n): if k == 0: return [()] return ((i,)+s for i in range(n) for s in sets(k-1, i))

So, for example, (line breaks added for clarity)

ghci> sets 2 8 [[1,0], [2,0],[2,1], [3,0],[3,1],[3,2], [4,0],[4,1],[4,2],[4,3], [5,0],[5,1],[5,2],[5,3],[5,4], [6,0],[6,1],[6,2],[6,3],[6,4],[6,5], [7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6]]

What would be the "C++ way" of doing this? Note that I'm not asking how to solve the problem. I'm asking about what data types would be considered "normal" by C++ programmers.

(For reference, I'm vaguely familiar with C++ and somewhat familiar with C.)

解决方案

Here's a naive, recursive approach, which implements the classical combinatorial identity:

binom(n + 1, k + 1) = binom(n, k + 1) + binom(n, k)

#include <set> typedef std::set<int> intset; std::set<intset> subsets(std::size_t k, intset s) { if (k == 0 || s.empty() || s.size() < k) { return { { } }; } if (s.size() == k) { return { s }; } auto x = *s.begin(); s.erase(s.begin()); std::set<intset> result; for (auto & t : subsets(k - 1, s)) { auto r = std::move(t); r.insert(x); result.insert(std::move(r)); } for (auto & t : subsets(k, s)) { results.insert(std::move(t)); } return result; }

Usage:

auto ss = subsets(3, {0, 1, 2, 3, 4});

Complete example:

#include <iostream> #include <string> #include <prettyprint.hpp> int main(int argc, char * argv[]) { if (argc != 3) return 1; auto k = std::stoul(argv[1]); auto n = std::stoul(argv[2]); intset s; for (auto i = 0U; i != n; ++i) s.insert(i); std::cout << subsets(k, s) << std::endl; }