m个数中取n个数的组合算法

Question

请问各个大牛有哪些好的算法来实现m个数中取n个数的组合？

比如有10个数{1,2,3,4,5,6,7,8,9,10}然后抽取6个数进行组合

如下：

1 2 3 4 5 6 

1 2 3 4 5 7

1 2 3 4 5 8

1 2 3 4 5 9

......

是组合，所以不考虑排列问题

Answer 1

n取m得到数量：

def ngetm(n,m):     
    if m==n:         
        return #6897BB;">1 6897BB;">     
    elif m==#6897BB;">0: CC7832;font-weight:bold;">        
        return #6897BB;">1 6897BB;">     
    else:         
        return ngetm(n-#6897BB;">1CC7832;">,m-#6897BB;">1)+ngetm(n-6897BB;">1,m)

list取m得到所有结果：

def ngetmprint(list,ans#CC7832;">,m): CC7832;font-weight:bold;">    
    if m==len(list):
        ans = ans + list         
        print ans      
    elif m==0:         
        print ans     
    else:         
        ngetmprint(list[1:],ans+list[0:1],m-1)         
        ngetmprint(list[1:],ans,m)

Answer 2

/**
	 * 组合问题： 输出从数组a的n个元素中选出m个元素的组合
	 * @param a	给定数组
	 * @param b	组合结果  (b中存放的是元素在a中的编号)
	 * @param n	
	 * @param m
	 * @param M	常量=m 记录a中元素个数
	 * 
	 * 思路：1.从n个元素中选出序号最大的数，然后在剩下的(n-1)个元素中选(m-1)个
	 * 	  当m=1时，倒序输出数组b；
	 *      2.从n个元素中选出编号次小的数，重复第1步。
	 */
	public static void comb( int[] a, int[] b, int n, int m, final int M ){
		for( int i=n; i>=m; i--){
			b[m-1] = i-1;
			if( m>1 ){
				comb(a,b,i-1,m-1,M);
			}else{
				for( int j=M-1; j>=0; j-- ){
					System.out.print(a[b[j]]+" ");
					if( j==0 ) 
						System.out.println();
				}
			}
		}
	}

Answer 3

m!/(m-n)!/n!

m>n

如果m=n, 数量是1

Answer 4

求数量，还是随机抽取，还是作为什么？

Answer 5

递归关系是这个 

m 中取n个元素等于 

取m中的第一个元素， 再在剩余的m-1中取n-1个元素 

或者 在剩余的m-1个中取 n个元素

C(m, n) = C(m-1, n-1) + C(m-1, n)

特例就是：

当n为0的时候， 以及当m小于n的时候

m = 10
n = 4
p = range(0, m)

def getC(seq, k):
    if k == 0:
        return [[]]
    if len(seq) == k:
        return [list(seq)]
    res = []
    for i in range(0, len(seq)-k+1):
        temp = getC(seq[i:], k-1)
        for t in temp:
            res.append([seq[i]]+t)
    return res
r = getC(p, n)
print r
        

Answer 6

哎~~~~木人来看哦

Answer 7

网上很多啊，随便找找都有了。

http://blog.sina.com.cn/s/blog_49b05ad00100dkbi.html

递归写写好了。

Answer 8

网上很多啊，随便找找都有了。

http://blog.sina.com.cn/s/blog_49b05ad00100dkbi.html

递归写写好了。