标题: 求一个组合的问题 [打印本页] 作者: shiyiming 时间: 2008-10-15 13:12 标题: 求一个组合的问题 现有数据集aa
n1
a
b
c
d
e
f
g
现在想求变量n1的各种组合，比如a b，a c,a d, a e, a f,a g,abc,abd-----等等作者: shiyiming 时间: 2008-10-15 21:30 标题: Re: 求一个组合的问题 all subsets
<!-- m --><a class="postlink" href="http://listserv.uga.edu/cgi-bin/wa?A2=ind0606c&L=sas-l&F=&S=&P=3815">http://listserv.uga.edu/cgi-bin/wa?A2=i ... &S=&P=3815</a><!-- m -->
[code:1xko7hvu]
data aa;
input n1 $ 1;
call symputx('nobs', _N_);
datalines;
a
b
c
d
e
f
g
;
run;
proc transpose data=aa out=bb;
var n1;
run;
proc means data=bb noprint;
class col1-col&nobs;
output out=pattern(drop=_type_ _freq_);
run;
[/code:1xko7hvu]作者: shiyiming 时间: 2008-10-16 07:37 标题: Re: 求一个组合的问题 [code:3k1d7ljr]%let chars=abcdefg;
%let len=%length(&chars);
data ahuige(keep=chars);
do i=0 to 2**&len-1;
chars=put("&chars",&len..);
do j=1 to &len;
if substr(put(i,binary&len..),j,1)^=1 then substr(chars,j,1)=' ';
end;
output;
end;
run;[/code:3k1d7ljr]作者: shiyiming 时间: 2008-10-16 11:07 标题: Re: 求一个组合的问题 太强了，感谢２位兄弟作者: shiyiming 时间: 2008-10-17 00:48 标题: Re: 求一个组合的问题 I forgot binary representation. Here's another one. Is it possible to reduce the time complexity from O(n*2^n) to O(2^n) ?
[code:3b0s05xp]
proc iml;
chars = {'a' 'b' 'c' 'd' 'e' 'f' 'g'};
x = repeat(0,1,ncol(chars));
do xi=1 to 2**ncol(chars)-1;
if x[1]=0 then x[1]=1;
else do;
n0 = x[>:<]; *the position of first 0;
x[1:(n0-1)] = 0;
x[n0] = 1;
end;
y=rowcatc((chars[loc(x=1)])`);
print x / y;
end;
quit;
[/code:3b0s05xp]作者: shiyiming 时间: 2008-10-17 06:45 标题: Re: 求一个组合的问题 From the appearance of your source code it seems the inner loop is gone away. I have no idea about iml. But it seems the function rowcatc does this for you(correct me if I am wrong).
however, the rowcatc itself or its counterpart should have a mechanism to scan the whole vector and concatenate them conditionally.
It might not reduce the complexity substantially. At least on my computer it takes more time to run. Anyway, it is a nice try buddy.作者: shiyiming 时间: 2008-10-17 12:48 标题: Re: 求一个组合的问题 I was just mimicking your code, so the inner loop is still there. I think the 'loc' function needs to visit every entry of vector 'x' to identify all the 1's, also 'x[>:<]' may have to search the whole vector to identify the first 0.
Anyway, my question is simply STUPID, because 2^n is already so bad that adding a factor of n doesn't make it worse.