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

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

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.）}

来源

2012-09-09 Snowball

忘记对C有点熟悉，它根本无法帮到你。 – Puppy

我意识到这是一个旧帖子，但我注意到没有人提出迭代算法来做到这一点。查看[my note]（http://blazsovdat.com/subsets.pdf）关于生成n集的所有k-子集以描述这样的算法和[它的实现]（https://gist.github.com/blazs/9638794）。（事实证明，它基本上与Knuth在其第4卷中描述的算法之一相同）。 – blazs

这里的一个幼稚，递归方法，它实现了经典组合身份：

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-09 21:40:08

集所有子集的概念被称为power set，和维基百科已经颇有几分上写的。其中一部分甚至专门用于algorithms做您想做的事。这个特殊的问题要求功率集subsets of limited cardinality。你应该使用std::set。

来源

2012-09-09 22:07:52 oldrinb

的快速实现在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-09 22:23:22 Alexandros

罗塞塔代码an implementation，通过采取列表0, 1, ..., n-1的排列的第一k项工作。它使用C++ STL。

来源

2012-09-10 00:21:13 Snowball

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

回答

相关问题