发信人: GzLi (笑梨), 信区: DataMining
标 题: [合集]请教求子集的算法
发信站: 南京大学小百合站 (Fri May 31 19:22:43 2002), 站内信件
billylin (fat billy) 于Mon May 27 09:14:48 2002提到：
对于集合{1,2,...,n},如何求出它所有的子集?
很明显子集总数为:C(n,1)+C(n,2)+...+C(n,n)=2^n-1
用程序来输出,我的想法是用n-1个循环,第i个循环输出C(n,i)个子集
但是,我们知道,对于未知的n,程序中是不可能写出n-1个循环的,计算机程序只能写
出固定个数的循环体
所以,我想请教一个新方法,可以求出一个集合所有子集的普适算法.
谢了
eastcamel (Happy Digger!) 于Mon May 27 09:26:03 2002提到：
可以考虑用递归的方式，虽然效率比较低
如果n不是很大，也可以考虑用m个的固定循环体，m>=n
billylin (fat billy) 于Mon May 27 10:07:27 2002提到：
嗯,现在看来apriori算法也不见得高效,我在用delphi+sql server实现它时,碰到的
最棘手的问题居然就是这个求子集算法,即使用递归也很难写得无bug
不知大家是如何实现apriori算法的
jimo (寂寞) 于Mon May 27 12:12:54 2002提到：
apriori中求子集要比他的问题中的要简单
jimo (寂寞) 于Mon May 27 13:02:49 2002提到：
void combination(int a,int b,int *c)//产生组合
{
if (a==b)
{
for (int i=1;i tfile int j=c[0];
for(i=j;i>=1;i--)
tfile tfile }
else if (b==1)
{
for (int i=1;i {
tfile int j=c[0];
for(int iii=j;iii>=1;iii--)
tfile tfile }
}
else
{
combination(a-1,b,c);
int *temp=new int[10];
for (int ii=0;ii temp[ii]=c[ii];
temp[temp[0]+1]=a;
temp[0]++;//长度加一
combination(a-1,b-1,temp);
}
}
这个大致能实现
buddha (大佛) 于Mon May 27 20:26:27 2002)
提到：
apriori算法的中好像不必用求组合，dhp中倒是要的。在组合数学书中有的，我就是在那
找的。
jimo (寂寞) 于Mon May 27 21:41:05 2002提到：
问问题的人是不是想实现fptree 呢
billylin (fat billy) 于Mon May 27 21:58:20 2002提到：
嗯
我觉得fptree实现的数据结构很难,每个节点的指针个数都不知道,还请指点
jimo (寂寞) 于Mon May 27 21:59:53 2002提到：
呵呵
向量吧
但是内存的浪费是有的
或者二叉树
这个我也实现了
但是性能上要差一些的
bluefinger (人有我无) 于Mon May 27 22:41:09 2002)
提到：
我是用试探-回溯法求的，不是实现Apriori，是在粗集求简化规则时碰到的，好像也差不
多，几个月以前做的，具体程序现在找不到了。
基本思路是n个循环，每个循环里用一个变量count记录已找到的元素个数，一个变量pos记
录当前位置，然后从第一个元素开始搜索，找到一个解后，修改最后一个元素的值，如果
已到最后，则pos-1，修改元素值，直至回溯到第一个元素。
是不是有更好的办法？请高手赐教
fervvac (高远) 于Mon May 27 23:40:16 2002提到：
for i = 0 to 2^n - 1
for j = 0 to n - 1
if GET_BIT(i, j)
print asc('A'+j)
print "\n"
fervvac (高远) 于Mon May 27 23:43:08 2002提到：
To be lazy, use vector.
BTW, those cross linking ptrs acan be avoided. See their H-miner paper and ...
jimo (寂寞) 于Tue May 28 11:12:30 2002提到：
and what a ?
hehe
billylin (fat billy) 于Wed May 29 15:05:15 2002提到：
~~~~~~~~~~~~~~~~不好意思,这句是什么意思,可否解释一下,谢谢
fervvac (高远) 于Wed May 29 16:03:07 2002提到：
A macro to get the j-th bit of the binary representation of i, easily
done by bit shifting and masking.
fervvac (高远) 于Thu May 30 14:21:10 2002提到：
Just cross this site:
http://www.cis.upenn.edu/~wilf/lecnotes.html
