c++ - 生成 {0, 1, 2, ... n-1} 的所有大小为 k 的子集

Question

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

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

或者在 Python 中:

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

因此，例如，(为清楚起见添加了换行符)

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]]

这样做的“C++ 方式”是什么？请注意，我不是在问如何 解决问题。我问的是 C++ 程序员认为哪些数据类型是“正常的”。

^{(供引用，我对C++有点熟悉，对C有点熟悉。)}

Answer 1

这是一个朴素的递归方法，它实现了经典的组合恒等式:

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;
}

用法:

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 << subsets(k, s) << std::endl;
}