一个组合问题

mathe

计算机搜索有很多结果
0 1 4 11 29;0 2 8 17 22
0 1 4 11 29;0 2 21 26 35
0 1 13 31 38;0 2 8 17 22
0 1 13 31 38;0 2 21 26 35
0 1 15 19 25;0 2 5 13 34
0 1 15 19 25;0 2 9 30 38
0 1 15 19 25;0 3 11 32 39
0 1 17 23 27;0 2 5 13 34
0 1 17 23 27;0 2 9 30 38
0 1 17 23 27;0 3 11 32 39
0 2 8 17 22;0 3 10 28 40
0 2 21 26 35;0 3 10 28 40
我们可以以
0 1 4 11 29;0 2 8 17 22
为例子
上面对应两个模式，每个模式中每个数都可以加上0~40中任意一个数并且模41可以形成共82种模式。
这82个模式中，0~40每个数都正好在10个模式中出现。
于是我们把82个模式看成82个人，0~40看成41次会议，那么82个人可以召开41次会议，每次会议正好10个人，而没有两个人参加相同的会议

mathe

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. #define MAXV 41
   
5. #define TSIZE 91390
   
6. 
   
7. #define INVALID 0xFFFFFFFFFFFFFFFFLL
   
8. unsigned data[TSIZE];
   
9. signed long long result[TSIZE];
   
10. int dc;
    
11. signed long long alldiff(unsigned int x[5])
    
12. {
    
13.     signed long long r=0ll;
    
14.     int i,j;
    
15.     for(i=0;i<5;i++)for(j=i+1;j<5;j++){
    
16.         long long l1 = 1ll<<(x[j]-x[i]);
    
17.         if(r&l1)return INVALID;
    
18.         r|=l1;
    
19.         l1 = 1ll<<(MAXV-(x[j]-x[i]));
    
20.         if(r&l1)return INVALID;
    
21.         r|=l1;
    
22.     }
    
23.     return r;
    
24. }
    
25. 
    
26. void init()
    
27. {
    
28.     unsigned int i[5];
    
29.     i[0]=0;
    
30.     for(i[1]=i[0]+1;i[1]<MAXV;i[1]++){
    
31.        for(i[2]=2*i[1]+1;i[2]<MAXV;i[2]++){
    
32.            for(i[3]=i[2]+i[1]+1;i[3]<MAXV;i[3]++){
    
33.                for(i[4]=i[3]+i[1]+1;i[4]<MAXV;i[4]++){
    
34.                   signed long long r = alldiff(i);
    
35.                   data[dc]=((i[1]<<24)|(i[2]<<16)|(i[3]<<8)|(i[4]<<0));
    
36.                   result[dc]=r;
    
37.                   dc++;
    
38.                }
    
39.            }
    
40.        }
    
41.     }
    
42. }
    
43. 
    
44. void output(unsigned x, unsigned y)
    
45. {
    
46.     printf("0 %d %d %d %d;", x>>24, (x>>16)&255, (x>>8)&255, x&255);
    
47.     printf("0 %d %d %d %d\n",y>>24, (y>>16)&255, (y>>8)&255, y&255);
    
48. }
    
49. 
    
50. int main()
    
51. {
    
52.     int i,j;
    
53.     init();
    
54.     printf("dc=%d\n",dc);
    
55.     for(i=0;i<dc;i++){
    
56.       if(result[i]==INVALID)continue;
    
57.       for(j=i+1;j<dc;j++){
    
58.         if((result[i]&result[j]) == 0ll){
    
59.             output(data[i],data[j]);
    
60.         }
    
61.       }
    
62.     }
    
63. }
    

复制代码

王守恩

mathe 发表于 2018-4-26 11:38
计算机搜索有很多结果
0 1 4 11 29;0 2 8 17 22
0 1 4 11 29;0 2 21 26 35

我还是厚着脸皮问：A(82,18,10)=41应该有的，但 ,有A(8, ? ,3)=8吗？

补充内容 (2018-4-27 08:46):

谢谢mathe！谢谢宝贵的资料！ A(82,18,10)=41是有的，A(8, ? ,3)=8也是有的。节点没有问题，前面有个路灯，心里踏实多了。

Sirius

谢谢math老师，构造很巧妙。