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重循環求所有排列
 2void 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中出現過
44int 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, 遞歸求所有排列
 2void 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//遞歸取得下一個數字
17void 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}

題2：0、1、2、3、4、5、6、7、8、9十個數字中，求所有6個不重復數字的組合：

 1void 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//取得所有排列
10void 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//打印排列
27void 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位的更大的數；應用：在用位串表示集合的子集時 
39unsigned 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}

 

補充問題：
1. 上面問題2的解法中，使用了unsigned int來進行位操作，但在求C(N,M)時，如果N>32，該怎么辦呢？(考慮自己實現BitArray)
2. 一個給定的集合有100萬個元素，其中每個元素又是由1～1000萬之間的100萬個不重復數字組成的集合，如果對這些集合進行和并操作，求最少有哪些集合能構成1..1000W這個全集？（06年底，同學的一道baidu面試題，大致意思是這樣的）