对组合排列问题的小结

(1)求组合排列数
问题一:
从n个不同数中取k个的组合数,排列数?
简单组合排列公式
问题二:
从n1个a1,n2个a2,n3个a3,……,nk个ak中(a1,a2……允许相等):
取k个数的组合方案数?(用母函数求解)
取k个的排列方案数?(指数型母函数)
(2)输出组合排列方案
问题三:
n个不同数取k个的全部组合?
可以使用dfs求解

从n个不同元素中取k个进行组合的方案

看了《组合数学及其应用》第一章之后用dfs实现了下输出从n个不同元素中取k个进行组合的方案,具体思想可参考这篇博文:http://masoi.blog.sohu.com/98842004.html
n个不同元素取k个,假设组合升序排列,则显然有如下性质:(输入数组a[]已升序排列)
(1)第k个数最大取到a[n],第k-1个数最大取到a[n-1]……第j个数最大取到a[n-(k-j)]……第1个数最大取到a[n-(k-1)]。
(2)第j个数比第j-1个数大。
根据以上两点不难写出dfs程序。
特别的,当从x,x+1,x+2,……,x+n-1这n个连续元素中取k个元素时有更特殊的解法。(这里的“连续元素”可以扩展,可以是等差数列,并不一定元素间只相差1,当然本人没实现过,不敢说这句话正确)