本文介绍了生成{0,1,2，... n-1}的所有大小k个子集，的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 我想生成所有基数 k {0,1,2，...，n-1}的子集在C ++。在Haskell中，我会： sets 0 n = [[]] 设置kn = [i：s | 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;} 这篇关于生成{0,1,2，... n-1}的所有大小k个子集，的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！
