从给定的一组数字中生成选择的最佳方法是什么？
从给定的一组数字中生成选择的最佳方法是什么？
提问于 2010-08-04 20:35:26
例如，如果让它在1到5之间做出所有选择，答案是这样的。
1,2,3,4,5,
1-2,1-3,1-4,1-5,2-3,2-4,2-5,3-4,3-5,4-5,
1-2-3,1-2-4,1-2-5,1-3-4,
.....,
1-2-3-4-5.有没有人能给出一个快速算法？
回答 6
Stack Overflow用户
回答已采纳
发布于 2010-08-04 20:41:24
只需生成从1到2^N -1的所有整数(如果要包含空集，则生成0)。您的集合由数字中的集合位表示。例如，如果您有5个元素{A，B，C，D，E}，数字6= 00110将表示子集{C，D}。
Stack Overflow用户
发布于 2010-08-04 21:11:35
你想找到powerset
In mathematics, given a set S, the power set (or powerset) of S, written ,
P(S), , is the set of all subsets of S有一种算法可以在这个link上找到功率集。
You basically take first element say 1 and find a all subsets {{},{1}}. Call this
power set
Take next element 2 and add to powerset and get {{2},{1,2}} and take union
with powerset.
{{},{1}} U {{2},{1,2}} = {{},{1},{2},{1,2}}但在上面的答案中描述了一种简单的方法。Here是一个详细解释它的链接。
Stack Overflow用户
发布于 2010-08-04 21:36:10
最快的是使用template metaprogramming，它会用编译时间和代码大小来换取执行时间。但这只适用于数量较少的组合，并且您必须提前了解它们。但是，你说的是“快速”:)
#include <iostream>
using namespace std;
typedef unsigned int my_uint;
template <my_uint M>
struct ComboPart {
ComboPart<M-1> rest;
void print() {
rest.print();
for(my_uint i = 0; i < sizeof(my_uint) * 8; i++)
if(M & (1<<i)) cout << (i + 1) << " ";
cout << endl;
}
};
template <>
struct ComboPart<0> {
void print() {};
};
template <my_uint N>
struct TwoPow {
enum {value = 2 * TwoPow<N-1>::value};
};
template <>
struct TwoPow<0> {
enum {value = 1};
};
template <my_uint N>
struct Combos {
ComboPart<TwoPow<N>::value - 1> part;
void print() {
part.print();
}
};
int main(int argc, char *argv[]) {
Combos<5> c5 = Combos<5>();
c5.print();
return 0;
}这个函数在编译时构造所有的组合。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3405511
复制相关文章
相似问题
腾讯云开发者
