设计算法以求解从集合{1..n}中选取k(k

设计算法以求解从集合{1..n}中选取k(k
设计算法以求解从集合{1..n}中选取k(k

设计算法以求解从集合{1..n}中选取k(k
C(k,n-1)=∏(n-k,n-1)/k!
C(k-1,n-1)=∏(n-k+1,n-1)/(k-1)!
C(k-1,n)+C(k-1,n-1)
=∏(n-k,n-1)/k!+∏(n-k+1,n-1)/(k-1)!
=∏(n-k,n-1)/k!+k·∏(n-k+1,n-1)/k!
=[(n-k)·∏(n-k+1,n-1)!+k·∏(n-k+1,n-1)]/(k-1)!
=[n·∏(n-k+1,n-1)]/k!
=∏(n-k+1,n)]/k!
=C(k,n)
即：C(k-1,n)+C(k-1,n-1)=C(k,n)
说简单点,就是杨辉三角形的元素算法.
此原理应用到你的问题上,重点是：结果集合的每个元素又是个集合.
若通用集合类Set(其实java中Set就是)；
new Set{value...}为构造方法,-{value..}为集合差,+{value...}为集合和,Set(i)和集合第i个元素；
对于n个元素的集合Sn,如果有函数Set combine(k,Sn),产生n个元素中选k个元素集合的集合；那么,当a是n个元素中的任意一个时,combine(k,Sn)=combine(k,Sn-{a})+combine(k-1,Sn-{a}).
由此可以产生递归算法：
Set Sn=new Set{a0,a1,...an-1};
Set result=Sn.combine(k,Sn);
.
.
function Set combine(int count,Set S){
if(count==S.size()){
return new Set{S};//这是集合S仅为结果集的一个元素
}
if(count+1==S.size()){
Set result=new Set{};
for(Element a:S){
result+=new Set{S-{a}};//集合依次排除一个元素产生的子集作为结果的一个元素
}
return result;
}
Set S2=combine(count-1,S-S(0));//对应YH公式的后一项,S(0)为集合S的第一个元素
for(Set Si:S2){
Si+={S(0)};//Si是缺了一个元素的
}
Set S1=combine(count,S-S(0));//这个是个数整好的,YH公式的前一项
return S1+S2;//YH公式
}
这个问题比较有意思,不知道谁出的.没有中学组合知识或YH公式,真困难了.
要是谁有更好算法,不妨交流一下.
这题分给的够低了,纯属兴趣做一下玩.