生成{0,1,2，... n-1}的所有大小k个子集， [英] Generating all size k subsets of {0, 1, 2, ... n-1}

问题描述

我想生成所有基数 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;
}


                        
这篇关于生成{0,1,2，... n-1}的所有大小k个子集，的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！