N个元素的集合中，任选M个元素所构成的排列P(M in N)、组合C(M in N)
题1：0、1、2、3、4、5、6、7、8、9十个数字中，求所有非0开头的6个不重复数字的排列。
法1：很邪恶很强大的循环
1
//
M in N, M重循环求所有排列
2
void
GetSixNumberSerial1()
3
{
4
int totel = 0;
5
int i[6] = {1,0,0,0,0,0};//如果允许0开头(即求全排列)，则将i[0]设成0即可
6 for(;i[0]<=9;i[0]++)
7 {
8 for(i[1]=0;i[1]<=9;i[1]++)
9 {
10 if(!Exist(i,1))
11 {
12 for(i[2]=0;i[2]<=9;i[2]++)
13 {
14 if(!Exist(i,2))
15 {
16 for(i[3]=0;i[3]<=9;i[3]++)
17 {
18 if(!Exist(i,3))
19 {
20 for(i[4]=0;i[4]<=9;i[4]++)
21 {
22 if(!Exist(i,4))
23 {
24 for(i[5]=0;i[5]<=9;i[5]++)
25 {
26 if(!Exist(i,5))
27 {
28 //printf("%d%d%d%d%d%d\n",i[0],i[1],i[2],i[3],i[4],i[5]);
29 totel++;
30
}
31 }
32 }
33 }
34 }
35 }
36 }
37 }
38 }
39 }
40 }
41 printf("Totle:%d\n", totel);
42
}
43
//
判断index是否在items中出现过
44
int
Exist(
int
items[],
int
index)
45
{
46 int i=0;
47 for(;i<index;i++)
48 {
49 if(items[i]==items[index])
50 return 1;
51 }
52 return 0;
53}
//
M in N, M重循环求所有排列
2
void
GetSixNumberSerial1()3
{4
int totel = 0;5
int i[6] = {1,0,0,0,0,0};//如果允许0开头(即求全排列)，则将i[0]设成0即可6
for(;i[0]<=9;i[0]++)7
{8
for(i[1]=0;i[1]<=9;i[1]++)9
{10
if(!Exist(i,1))11
{12
for(i[2]=0;i[2]<=9;i[2]++)13
{14
if(!Exist(i,2))15
{16
for(i[3]=0;i[3]<=9;i[3]++)17
{18
if(!Exist(i,3))19
{20
for(i[4]=0;i[4]<=9;i[4]++)21
{22
if(!Exist(i,4))23
{24
for(i[5]=0;i[5]<=9;i[5]++)25
{26
if(!Exist(i,5))27
{28
//printf("%d%d%d%d%d%d\n",i[0],i[1],i[2],i[3],i[4],i[5]);29
totel++;30
}31
}32
}33
}34
}35
}36
}37
}38
}39
}40
}41
printf("Totle:%d\n", totel);42
}
43
//
判断index是否在items中出现过
44
int
Exist(
int
items[],
int
index)45
{46
int i=0;47
for(;i<index;i++)48
{49
if(items[i]==items[index])50
return 1;51
}52
return 0;53
}
法2：很邪恶很强大的递归
1
//
M in N, 递归求所有排列
2
void
GetSixNumberSerial2()
3
{
4 int items[6]={0,0,0,0,0,0};
5 int depth = 1;
6 int totel=0;
7 int i=1;//如果允许0开头(即求全排列)，则将i初始化为0即可
8 for(;i<=9;i++)
9 {
10 items[depth-1] = i;
11 GetNextNumber(items,depth+1, &totel);
12 }
13 printf("Totel:%d\n", totel);
14}
15
16
//
递归取得下一个数字
17
void
GetNextNumber(
int
items[],
int
depth,
int
*
totel)
18
{
19 if(depth==7)//只取6位数
20 {
21 //printf("%d%d%d%d%d%d\n",items[0],items[1],items[2],items[3],items[4],items[5]);
22 *totel += 1;
23 return;
24 }
25 else
26 {
27 int i=0;
28 for(i=0;i<=9;i++)
29 {
30 items[depth-1]=i;
31 if(!Exist(items,depth-1))//使用上面法1中的Exist函数
32 {
33 items[depth-1]=i;
34 GetNextNumber(items, depth+1, totel);
35 }
36 }
37 }
38}
//
M in N, 递归求所有排列
2
void
GetSixNumberSerial2()3
{4
int items[6]={0,0,0,0,0,0};5
int depth = 1;6
int totel=0;7
int i=1;//如果允许0开头(即求全排列)，则将i初始化为0即可8
for(;i<=9;i++)9
{10
items[depth-1] = i;11
GetNextNumber(items,depth+1, &totel);12
}13
printf("Totel:%d\n", totel);14
}
15
16
//
递归取得下一个数字
17
void
GetNextNumber(
int
items[],
int
depth,
int
*
totel)18
{19
if(depth==7)//只取6位数20
{21
//printf("%d%d%d%d%d%d\n",items[0],items[1],items[2],items[3],items[4],items[5]);22
*totel += 1;23
return;24
}25
else26
{27
int i=0;28
for(i=0;i<=9;i++)29
{30
items[depth-1]=i;31
if(!Exist(items,depth-1))//使用上面法1中的Exist函数32
{33
items[depth-1]=i;34
GetNextNumber(items, depth+1, totel);35
}36
}37
}38
}
题2：0、1、2、3、4、5、6、7、8、9十个数字中，求所有6个不重复数字的组合：
1
void
GetSixNumberCombination()
2
{
3 int length = 10;
4 char s[10]={'0','1','2','3','4','5','6','7','8','9'};
5 int sub = 6;
6 GetAllSubCollection(s,length,sub);
7}
8
9
//
取得所有排列
10
void
GetAllSubCollection(
char
s[],
int
length,
int
sub)
11
{
12 unsigned min = 0x3F; //00 0011 1111
13 unsigned max = 0x3F0; //11 1111 0000
14 unsigned result =min;
15
16 int i;
17 int j=0;
18 for(i=min; i<=max; i=snoob(i))
19 {
20 printSubCollection(s, i, length);
21 j++;
22 }
23 printf("Totel:%d", j);
24}
25
26
//
打印排列
27
void
printSubCollection(
char
s[], unsigned
int
result,
int
length)
28
{
29 int i;
30 for(i=0; i<length; i++)
31 {
32 if(result & 1<<i)
33 printf("%c", s[i]);
34 }
35 printf("\n");
36}
37
38
//
获取下一个具有同样数量的1位的更大的数；应用：在用位串表示集合的子集时
39
unsigned snoob(unsigned x)
40
{
41 unsigned smallest, ripple, ones;//e.g.: x=XXX0 1111 0000
42 smallest = x & -x; // 0000 0001 0000
43 ripple = x + smallest; // XXX1 0000 0000
44 ones = x ^ ripple; // 0001 1111 0000
45 ones = (ones >> 2) / smallest; // 0000 0000 0111
46 return ripple | ones; // XXX1 0000 0111
47}
void
GetSixNumberCombination()2
{3
int length = 10;4
char s[10]={'0','1','2','3','4','5','6','7','8','9'};5
int sub = 6;6
GetAllSubCollection(s,length,sub);7
}
8
9
//
取得所有排列
10
void
GetAllSubCollection(
char
s[],
int
length,
int
sub)11
{12
unsigned min = 0x3F; //00 0011 111113
unsigned max = 0x3F0; //11 1111 000014
unsigned result =min;15
16
int i;17
int j=0;18
for(i=min; i<=max; i=snoob(i))19
{20
printSubCollection(s, i, length);21
j++;22
}23
printf("Totel:%d", j);24
}
25
26
//
打印排列
27
void
printSubCollection(
char
s[], unsigned
int
result,
int
length)28
{29
int i;30
for(i=0; i<length; i++)31
{32
if(result & 1<<i)33
printf("%c", s[i]);34
}35
printf("\n");36
}
37
38
//
获取下一个具有同样数量的1位的更大的数；应用：在用位串表示集合的子集时
39
unsigned snoob(unsigned x)40
{41
unsigned smallest, ripple, ones;//e.g.: x=XXX0 1111 000042
smallest = x & -x; // 0000 0001 000043
ripple = x + smallest; // XXX1 0000 000044
ones = x ^ ripple; // 0001 1111 000045
ones = (ones >> 2) / smallest; // 0000 0000 011146
return ripple | ones; // XXX1 0000 011147
}
补充问题：
1. 上面问题2的解法中，使用了unsigned int来进行位操作，但在求C(N,M)时，如果N>32，该怎么办呢？(考虑自己实现BitArray)
2. 一个给定的集合有100万个元素，其中每个元素又是由1～1000万之间的100万个不重复数字组成的集合，如果对这些集合进行和并操作，求最少有哪些集合能构成1..1000W这个全集？（06年底，同学的一道baidu面试题，大致意思是这样的）
本文转自Silent Void博客园博客，原文链接：http://www.cnblogs.com/happyhippy/archive/2008/03/10/1099342.html，如需转载请自行联系原作者
