第2个可能其实是有10个不重复的數,分成两步先选5个不重复的数,再在这5个数中选3个来组合最后的组合有多少种,其实这个问题就是在10个不同数中选3个来组合即C(10,3)=P(10,3)/(3!)=10!/((10-3)!)/3!= 10!/(7! * 3!) = 120
上面是以往的回答,下面是对其实质问题的回答
// 对N个元素取M组合的序数排列可能全输出函数
// 其返回一个二维数组数组长度是可能的数量,每个子数组有M个元素每个元素值代表其取原始数组的序号。
上面的代码利用了位运算其原理其实很简单,它产生一个N个元素的所有可能组合(对应于0至 111...111 的二进制数其中后面一个有N个1),然后过滤出恰好有M个1的数就是所要求的,所以这个效率其实不高的特别昰对于N很大时。
鉴于题主不理解上面实现的原理我再详细解释一下。
对于N个不重复元素其取得0个到N个元素组合的可能C(N,M) (0<=M<=N)如果用二进制表礻,就是用A(N)表示所有N位二进制数,包括N个0的即范围为[0,Power(2,N)-1]的非负整数集合,可以知道对于任何组合可能其实对应于一个A(N)内的整数记这个數C(N,M) 其还满足以下对应条件:
以 楼主 开始要求的在[1,2,3,4,5]中取3个都组合 举例就是:
对应的二进制数 对应十进制数 取得的组合可见,只要通过位运算來过滤出[0,Power(2,N)-1]的非负整数集合中满足只有M位为1的数就可以找到对应的组合这就是前面算法的实现原理。
其中过滤操作是通过位运算 X&1
实现具體过滤对应于:
,还是继续上面的例子以4,7、15分别为例这里n=5了,m=3,
4的二进制为100这时i=4所以有
7的二进制为111,这时i=7所以有
15的二进制为1111这时i=15所以有