猜排列问题

hujunhua

忘记了我居然在这个帖子下面回复了这么多。

mathe

试着测试一下随机mathe
代码假设Fans给出的目标数据就是按0,1,2,...,N-1顺序给出（但是mathe不知道）

1. #include <stdio.h>
   
2. #include <time.h>
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. #include <math.h>
   
6. #include <vector>
   
7. 
   
8. #ifndef N
   
9. #define N 20
   
10. #endif
    
11. 
    
12. #define TC 8
    
13. 
    
14. #define TARGET 1
    
15. 
    
16. struct Data{
    
17.     char v[N];
    
18.     int c;
    
19. };
    
20. 
    
21. std::vector<Data> usedlist;
    
22. std::vector<Data> leftlist;
    
23. char leftc;
    
24. char avail[N][N];
    
25. double tvalue;
    
26. double ve;
    
27. void init()
    
28. {
    
29.     tvalue = log(2*M_PI*N)/2+N*(log(N)-1)-log(TARGET);
    
30.     ve=exp(-1.0);
    
31.     int i,j;
    
32.     leftc=N;
    
33.     for(i=0;i<N;i++){
    
34.        for(j=0;j<N;j++)avail[i][j]=j;
    
35.     }
    
36. }
    
37. 
    
38. void dumpleft()
    
39. {
    
40.     int i;
    
41.     int j;
    
42.     for(i=0;i<leftlist.size();i++){
    
43.        printf("\n");
    
44.        for(j=0;j<N;j++)printf("%d ",leftlist[i].v[j]);
    
45.     }
    
46.     printf("\n");
    
47. }
    
48. 
    
49. char used[N];
    
50. char mc[N*N];
    
51. char umc[N*N];
    
52. Data tryv;
    
53. int depth;
    
54. void search()
    
55. {
    
56.     if(depth>=N){
    
57.         leftlist.push_back(tryv);
    
58.         return;
    
59.     }
    
60.     int i,j;
    
61.     for(i=0;i<usedlist.size();i++){
    
62.         if(mc[i]>usedlist[i].c||umc[i]>N-usedlist[i].c)return;
    
63.     }
    
64.     for(i=0;i<leftc;i++){
    
65.         int k = avail[depth][i];
    
66.         if(used[k]==0){//The value has not been used, try use it
    
67.             used[k]=1; tryv.v[depth]=k;if(k==depth)tryv.c++;
    
68.             for(j=0;j<usedlist.size();j++){
    
69.                 if(usedlist[j].v[depth]==k){
    
70.                     mc[j]++;
    
71.                 }else{
    
72.                     umc[j]++;
    
73.                 }
    
74.             }
    
75.             depth++;
    
76.             search();
    
77.             depth--;
    
78.             for(j=0;j<usedlist.size();j++){
    
79.                 if(usedlist[j].v[depth]==k){
    
80.                     mc[j]--;
    
81.                 }else{
    
82.                     umc[j]--;
    
83.                 }
    
84.             }
    
85.             used[k]=0;if(k==depth)tryv.c--;
    
86.         }
    
87.     }
    
88. }
    
89. 
    
90. void collect_lefts()
    
91. {
    
92.     depth=0;
    
93.     tryv.c=0;
    
94.     memset(used,0,sizeof(used));
    
95.     memset(mc,0,sizeof(mc));
    
96.     memset(umc,0,sizeof(umc));
    
97.     search();
    
98. }
    
99. 
    
100. int trygenrand(Data& d)
     
101. {
     
102.     char cused[N];
     
103.     memset(cused,0,sizeof(cused));
     
104.     int i,j,k;
     
105.     d.c=0;
     
106.     for(i=0;i<N;i++){
     
107.         j=rand()%leftc;
     
108.         int choice=-1;
     
109.         for(k=j;k<leftc;k++){
     
110.            if(cused[avail[i][k]]==0){choice=k;break;}
     
111.         }
     
112.         if(choice<0){
     
113.            for(k=0;k<j;k++){
     
114.               if(cused[avail[i][k]]==0){choice=k;break;}
     
115.            }
     
116.         }
     
117.         if(choice<0)return -1;
     
118.         cused[avail[i][choice]]=1;
     
119.         d.v[i]=avail[i][choice];
     
120.         if(d.v[i]==i)d.c++;
     
121.     }
     
122.     return 0;
     
123. }
     
124. 
     
125. void genrand(Data& d)
     
126. {
     
127.     while(trygenrand(d)<0);
     
128.     int i,j;
     
129.     usedlist.push_back(d);
     
130.     if(d.c==0){
     
131.        for(i=0;i<N;i++){
     
132.            for(j=0;j<leftc;j++){
     
133.                if(d.v[i]==avail[i][j])break;
     
134.            }
     
135.            if(j>=leftc){
     
136.                fprintf(stderr,"Internal error\n");
     
137.                exit(-1);
     
138.            }
     
139.            for(;j<leftc-1;j++){
     
140.                avail[i][j]=avail[i][j+1];
     
141.            }
     
142.        }
     
143.        leftc--;
     
144.     }
     
145.     double dd=ve;for(i=0;i<d.c;i++)dd/=(i+1);
     
146.     tvalue+=log(dd);
     
147. }
     
148. 
     
149. 
     
150. int main()
     
151. {
     
152.     Data d;
     
153.     srand(time(NULL));
     
154.     init();
     
155.     int t=0;
     
156.     while(leftc>TC){
     
157.         genrand(d);
     
158.         t++;
     
159.     }
     
160.     printf("try %d times to reach small probability, leftc = %d\n", t, leftc);
     
161.     collect_lefts();
     
162.     printf("Total %d left\n", (int)leftlist.size());
     
163.     dumpleft();
     
164. }
     

复制代码

测试了含20个数字，而mathe总是瞎猜直到听到12次Fans说你全错了位置在统计余下的可能
每次统计可能会很快（不到一秒）也可能会花费数分钟
试验结果
第一次:
try 72 times to reach small probability, leftc = 8
Total 1 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
第二次:
try 57 times to reach small probability, leftc = 8
Total 1 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

第三次:
try 53 times to reach small probability, leftc = 8
Total 1 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

第四次:
try 48 times to reach small probability, leftc = 8
Total 5 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
5 1 12 0 4 19 6 8 17 9 10 3 15 13 14 2 16 7 18 11
5 1 17 0 4 19 6 8 3 9 10 12 15 13 14 2 16 7 18 11
5 1 17 0 14 4 6 8 3 9 11 12 15 13 10 2 16 7 18 19
9 17 12 8 14 0 6 15 4 5 11 3 19 1 10 2 16 7 18 13
于是我们需要补猜一次
5 1 17 * 4 *  *************
就可以完全区分了。

第五次:
try 43 times to reach small probability, leftc = 8
Total 2 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 2 3 4 5 6 7 8 13 10 11 12 9 14 15 16 17 18 19

第六次:
try 42 times to reach small probability, leftc = 8
Total 2 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 2 3 4 5 6 7 8 9 19 11 12 13 14 15 16 17 18 10

第七次:
try 56 times to reach small probability, leftc = 8
Total 1 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

第八次:
try 70 times to reach small probability, leftc = 8
Total 1 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

第九次:
try 61 times to reach small probability, leftc = 8
Total 1 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

第十次
try 51 times to reach small probability, leftc = 8
Total 1 left

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

波动还是挺大的。
另外看来随机测试的次数还可以减少，提前分析规律会有好处。只是需要计算力非常强大，mathe远远不够。

mathe

1. #include <stdio.h>
   
2. #include <time.h>
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. #include <math.h>
   
6. #include <vector>
   
7. 
   
8. #ifndef N
   
9. #define N 12
   
10. #endif
    
11. 
    
12. #define MINTC 3
    
13. #define TC 6
    
14. 
    
15. #define TARGET 5
    
16. 
    
17. struct Data{
    
18.     char v[N];
    
19.     int c;
    
20.     bool operator==(const Data& d)const{
    
21.         int i; for(i=0;i<N;i++)if(v[i]!=d.v[i])return false;
    
22.         return true;
    
23.     }
    
24. };
    
25. 
    
26. std::vector<Data> usedlist;
    
27. std::vector<Data> leftlist;
    
28. char leftc;
    
29. char avail[N][N];
    
30. double tvalue;
    
31. double ve;
    
32. void init()
    
33. {
    
34.     tvalue = log(2*M_PI*N)/2+N*(log(N)-1)-log(TARGET);
    
35.     ve=exp(-1.0);
    
36.     int i,j;
    
37.     leftc=N;
    
38.     for(i=0;i<N;i++){
    
39.        for(j=0;j<N;j++)avail[i][j]=j;
    
40.     }
    
41. }
    
42. 
    
43. void filter(const Data& d)
    
44. {
    
45.     int i,j;
    
46.     std::vector<bool> valid;
    
47.     valid.resize(leftlist.size());
    
48.     for(i=0;i<valid.size();i++)valid[i]=true;
    
49.     for(i=0;i<leftlist.size();i++){
    
50.         int c=0;
    
51.         for(j=0;j<N;j++)if(d.v[j]==leftlist[i].v[j])c++;
    
52.         if(c!=d.c)valid[i]=false;
    
53.     }
    
54.     for(i=0,j=0;i<leftlist.size();i++){
    
55.         if(valid[i]){
    
56.            if(i>j)leftlist[j]=leftlist[i];
    
57.            j++;
    
58.         }
    
59.     }
    
60.     leftlist.resize(j);
    
61. }
    
62. 
    
63. void getMaxDist(Data& d)
    
64. {
    
65.     int i,j;
    
66.     int c[N];
    
67.     int used[N];d.c=0;
    
68.     for(i=0;i<N;i++)used[i]=0;
    
69.     for(i=0;i<N;i++){
    
70.         memset(c,0,sizeof(c));
    
71.         for(j=0;j<leftlist.size();j++){
    
72.              c[leftlist[j].v[i]]++;
    
73.         }
    
74.         int short_dist = 2*N+1, select=-1;
    
75.         for(j=0;j<N;j++){
    
76.              int v=2*c[j]-leftlist.size();
    
77.              if(v<0)v=-v;
    
78.              if(v<short_dist&&used[j]==0){
    
79.                  short_dist=v;select=j;
    
80.              }
    
81.         }
    
82.         if(select>=0){
    
83.             used[select]=1; d.v[i]=select;if(i==select)d.c++;
    
84.         }else d.v[i]=-1;
    
85.     }
    
86.     for(i=0,j=0;i<N;i++){
    
87.         if(d.v[i]<0){
    
88.             for(;j<N;j++){
    
89.                 if(used[j]==0){
    
90.                    used[j]=1;d.v[i]=j;if(i==j)d.c++;break;
    
91.                 }
    
92.             }
    
93.         }
    
94.     }
    
95.     do{
    
96.        for(i=0;i<usedlist.size();i++){
    
97.            if(d==usedlist[i]){
    
98.                break;
    
99.            }
    
100.        }
     
101.        if(i==usedlist.size())return;
     
102.        //If it has been used, randomly swap any two items
     
103.        int s=rand()%N; int t=rand()%(N-1); if(t>=s)t++;
     
104.        int tmp=d.v[s];d.v[s]=d.v[t];d.v[t]=tmp;d.c=0;
     
105.        for(i=0;i<N;i++)if(d.v[i]==i)d.c++;
     
106.     }while(1);
     
107. }
     
108. 
     
109. void output(const Data& d)
     
110. {
     
111.     int i;
     
112.     for(i=0;i<N;i++){
     
113.       printf("%d ",d.v[i]);
     
114.     }
     
115.     printf("\n");
     
116. }
     
117. 
     
118. void dumpleft()
     
119. {
     
120.     int i;
     
121.     int j;
     
122.     for(i=0;i<leftlist.size();i++){
     
123.        printf("\n");
     
124.        for(j=0;j<N;j++)printf("%d ",leftlist[i].v[j]);
     
125.     }
     
126.     printf("\n");
     
127. }
     
128. 
     
129. char used[N];
     
130. char mc[N*N];
     
131. char umc[N*N];
     
132. Data tryv;
     
133. int depth;
     
134. int countlimit;
     
135. int search()
     
136. {
     
137.     if(depth>=N){
     
138.         leftlist.push_back(tryv);
     
139.         if(leftlist.size()>countlimit)
     
140.             return -1;
     
141.         else return 0;
     
142.     }
     
143.     int i,j;
     
144.     for(i=0;i<usedlist.size();i++){
     
145.         if(mc[i]>usedlist[i].c||umc[i]>N-usedlist[i].c)return 0;
     
146.     }
     
147.     for(i=0;i<leftc;i++){
     
148.         int k = avail[depth][i];
     
149.         if(used[k]==0){//The value has not been used, try use it
     
150.             used[k]=1; tryv.v[depth]=k;if(k==depth)tryv.c++;
     
151.             for(j=0;j<usedlist.size();j++){
     
152.                 if(usedlist[j].v[depth]==k){
     
153.                     mc[j]++;
     
154.                 }else{
     
155.                     umc[j]++;
     
156.                 }
     
157.             }
     
158.             depth++;
     
159.             if(search()<0)return -1;
     
160.             depth--;
     
161.             for(j=0;j<usedlist.size();j++){
     
162.                 if(usedlist[j].v[depth]==k){
     
163.                     mc[j]--;
     
164.                 }else{
     
165.                     umc[j]--;
     
166.                 }
     
167.             }
     
168.             used[k]=0;if(k==depth)tryv.c--;
     
169.         }
     
170.     }
     
171.     return 0;
     
172. }
     
173. 
     
174. int collect_lefts(int limit)
     
175. {
     
176.     depth=0;
     
177.     tryv.c=0;
     
178.     memset(used,0,sizeof(used));
     
179.     memset(mc,0,sizeof(mc));
     
180.     memset(umc,0,sizeof(umc));
     
181.     leftlist.clear();
     
182.     countlimit=limit;
     
183.     return search();
     
184. }
     
185. 
     
186. int trygenrand(Data& d)
     
187. {
     
188.     char cused[N];
     
189.     memset(cused,0,sizeof(cused));
     
190.     int i,j,k;
     
191.     d.c=0;
     
192.     for(i=0;i<N;i++){
     
193.         j=rand()%leftc;
     
194.         int choice=-1;
     
195.         for(k=j;k<leftc;k++){
     
196.            if(cused[avail[i][k]]==0){choice=k;break;}
     
197.         }
     
198.         if(choice<0){
     
199.            for(k=0;k<j;k++){
     
200.               if(cused[avail[i][k]]==0){choice=k;break;}
     
201.            }
     
202.         }
     
203.         if(choice<0)return -1;
     
204.         cused[avail[i][choice]]=1;
     
205.         d.v[i]=avail[i][choice];
     
206.         if(d.v[i]==i)d.c++;
     
207.     }
     
208.     return 0;
     
209. }
     
210. 
     
211. void genrand(Data& d)
     
212. {
     
213.     while(trygenrand(d)<0);
     
214.     int i,j;
     
215.     usedlist.push_back(d);
     
216.     if(d.c==0){
     
217.        for(i=0;i<N;i++){
     
218.            for(j=0;j<leftc;j++){
     
219.                if(d.v[i]==avail[i][j])break;
     
220.            }
     
221.            if(j>=leftc){
     
222.                fprintf(stderr,"Internal error\n");
     
223.                exit(-1);
     
224.            }
     
225.            for(;j<leftc-1;j++){
     
226.                avail[i][j]=avail[i][j+1];
     
227.            }
     
228.        }
     
229.        leftc--;
     
230.     }
     
231.     double dd=ve;for(i=0;i<d.c;i++)dd/=(i+1);
     
232.     tvalue+=log(dd);
     
233. }
     
234. 
     
235. 
     
236. int main()
     
237. {
     
238.     Data d;
     
239.     srand(time(NULL));
     
240.     init();
     
241.     int t=0;
     
242.     while(t<N*N){
     
243.         genrand(d);
     
244.         t++;
     
245.         if(t>=MINTC){
     
246.            if(collect_lefts(100)>=0)break;
     
247.         }
     
248.     }
     
249.     printf("try %d times to reach small probability, leftc = %d\n", t, leftc);
     
250.     if(t>=N*N)
     
251.        collect_lefts(100);
     
252.     printf("Total %d left\n", (int)leftlist.size());
     
253.     dumpleft();
     
254.     while(leftlist.size()>1){
     
255.         getMaxDist(d);
     
256.         printf("Use: ");output(d);
     
257.         usedlist.push_back(d);
     
258.         filter(d);t++;
     
259.     }
     
260.     printf("Total tried %d times\n",t);
     
261. }
     

复制代码

试验了上面的代码，先随机，减少到一定程度，就用贪心法选择看上去还行的方法，实验结果基本上在2N次以内解决。但是N不能太大，不然程序运行时间会很长。其中参数TC建议选择接近N/2,越小代码跑得越快，但是前面随机使用次数会越多。而参数MINTC表示前面这么多次必然全随机，不会探测是否需要切换到贪心法