得出“15选5”的各种组合(组合生成算法)

长平狐 发布于 2012/06/08 12:34
阅读 666
收藏 0

今天有个网友问我组合数生成算法的问题,这个写的早,忘的都差不多了,给他回复了原理。刚好这段时间玩“155”,知道那个是随机的,概率问题(中就是中了,没中就是没中),没啥好分析的,可还是忍不住想计算下……

好,不废话了,下面开工。 

一、原理 

借助二进制计数的机制来进行比如字符串“123”中选出两个字符,如下计算:

1:二进制串为 0001

2: 0010

3: 0011 

4: 0100 

5: 0101 

6: 0110 

7: 0111 

8: 1000 

其中含有两个1的有 

3: 0011 

5: 0101 

6: 0110 

所以一共3个 

如果是1显示当前位置数据,不是1不显示,用字符串“123”匹配后结果为: 

 23 

1 3 

12 

即: 

23 

13 

12 

方法很土,不过可以实现功能,够一般用 

二、示例代码 

下面是C++的示例代码: 

View Code
1 /*
2 File : combination.cpp
3 Author : Mike
4 E-Mail : Mike_Zhang@live.com
5 */
6 #include <cstdio>
7 #include <cstdlib>
8 #include <iostream>
9 #include < string>
10 #include <vector>
11
12 using namespace std;
13
14 // 计算数据中二进制数据中1的个数
15 int count(unsigned int v)
16 {
17 int ret = 0;
18 while(v> 0)
19 {
20 v &= (v- 1);
21 ++ret;
22 }
23 return ret;
24 }
25
26 // 检测pos位置的二进制数据是否是1
27 bool check(unsigned int v, int pos)
28 {
29 unsigned int tmp= 0x01;
30 int sz = sizeof(v)* 8;
31 if(pos > sz)
32 {
33 printf( " pos > sz\r\n ");
34 return - 1;
35 }
36 tmp <<= pos;
37 return (v & tmp);
38 }
39
40 int main()
41 {
42 int i= 0,j= 0;
43 vector< string> vstr;
44 int szvstr = 0;
45 string str= "";
46 int num = 0;
47 cout<< " Input size of vector : ";
48 cin>>szvstr;
49
50 for(i= 0;i<szvstr;++i)
51 {
52 cout<< " Input string : ";
53 cin>>str;
54 vstr.push_back(str);
55 }
56 // 简单检查数据
57 while(num > szvstr or num == 0 )
58 {
59 cout<< " Input number : ";
60 cin>>num;
61 }
62
63 unsigned int counter = 1;
64 counter <<= szvstr;
65 int szUnsign = sizeof(unsigned int) * 8;
66
67 int total = 0;
68 // 输出组合结果
69 for(i= 0;i<counter;++i)
70 {
71 if(num == count(i))
72 {
73 for(j= 0;j<szUnsign && j < szvstr;++j)
74 {
75 if(check(i,j))
76 cout<<vstr[j] << " ";
77 }
78 cout<<endl;
79 ++total;
80 }
81 }
82 cout << " total = "<<total<<endl;
83 }

三、运行效果 

1、输入数据: 

首先输入集合的大小,比如15 

接下来输入每个元素,比如010203。。。15 

最后输入要选的组合,比如“155”的话就输入5 

具体如下: 

2、执行结果: 

这里会输出各种组合(“155”的各种组合),并输出各种组合的总个数,具体如下: 

  好,就这些了,希望对你有帮助。


原文链接:http://www.cnblogs.com/MikeZhang/archive/2012/03/20/CombinationTest.html
加载中
返回顶部
顶部