4

我想在 C++中生成所有基数k子集。{0, 1, 2, ..., n-1}在 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 有点熟悉。）

4

5 回答 5

4

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

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;
}
于 2012-09-09T21:40:08.787 回答
2

Rosetta Code 有一个实现，它通过获取k列表排列的第一个条目来工作0, 1, ..., n-1。它使用 C++ STL。

于 2012-09-10T00:21:13.693 回答
1

所有子集的集合的概念称为幂集，Wikipedia 对此有相当多的描述。其中一节甚至专门介绍了做你想做的事情的算法。这个特殊的问题要求幂集的有限基数的子集。您可能应该使用std::set.

于 2012-09-09T22:07:52.333 回答
1

在 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;
}
于 2012-09-09T22:23:22.880 回答
0

C++ 中的另一种递归解决方案。该函数ksubsets不希望输入 ( arr) 是一个集合，它可以由任何可以迭代的容器（在示例中我使用向量），并且它可以包含重复项。该函数生成k-sized存储在 中的数字的所有子集arr。子集存储在res.

#include<vector>

using namespace std;

void ksubsets(const vector<int>& arr, unsigned ksize, unsigned idx,
    vector<int>& tmp, vector<vector<int>>& res)
{
    if (ksize < 1) {
        res.push_back(tmp);
        return;
    }
    for (unsigned i = idx; i < arr.size(); i++) {
        tmp.push_back(arr[i]);
        ksubsets(arr, ksize - 1, i + 1, tmp, res);
        tmp.pop_back();
    }
}

int main()
{
    vector<int>arr = {1,2,3,4};
    vector<vector<int>> result;
    vector<int> cur;
    unsigned ksize = 3;
    ksubsets(arr, ksize, 0, cur, result); 

   // use here the result, it contains vectors {1,2,3}, {1,2,4},{1,3,4},{2,3,4}
}
于 2020-10-01T18:58:39.913 回答