生成{0,1,2，…，n-1}的所有大小k子集

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

我要生成所有的基数k子集{0,1,2，…在c++中,n - 1 }。在Haskell，我会做:

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

Or in Python:

或在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.

用“c++”怎么做呢?注意，我不是在问如何解决这个问题。我想问的是c++程序员认为哪些数据类型是“正常的”。

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

(作为参考，我对c++比较熟悉，对C也比较熟悉)

4 个解决方案

#1

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

#2

Rosetta Code has an implementation that works by taking the first k entries of permutations of the list 0, 1, ..., n-1. It uses the C++ STL.

Rosetta代码有一个实现，该实现通过获取列表0、1、…,n - 1。它使用c++ STL。

#3

The concept of a set of all subsets is called the power set, and Wikipedia has quite a bit written on it. One section is even dedicated to algorithms for doing what you want. This particular problem requests the subsets of limited cardinality of the power set. You should probably use std::set.

所有子集的概念都被称为幂集，*有很多关于它的文章。其中一个部分甚至专门用于实现您想要的功能的算法。这个特殊的问题要求幂集的基数有限的子集。您应该使用std::set。

#4

A quick implementation (using recursion) of this in C would be the following:

在C中快速实现(使用递归)如下:

#include <stdio.h>

#define N 8
#define K 3

void print_combination(int* combination, int k)
{
    int i;
    for (i = 0; i < k; i++){
        printf("%d ", combination[i]);
    }
    printf("\n");
}

void find_all_combinations(int idx, int* in_use, int* combination,
        int n, int k)
{
    int i;
    if (idx == k){
        print_combination(combination, k);
        return;
    }

    for (i = 0; i < n; i++){
        if (in_use[i]){
            continue;
        }

        in_use[i] = 1;
        combination[idx++] = i + 1;

        find_all_combinations(idx, in_use, combination, n, k);

        combination[--idx] = 0;
        in_use[i] = 0;
    }
}

int main(void)
{
    /* Ensure that the arrays are initialized with zeroes. */
    int in_use[N] = {0};
    int curr_combination[K] = {0};
    find_all_combinations(0, in_use, curr_combination, N, K);

    return 0;
}

#1