忘记了我居然在这个帖子下面回复了这么多。:o
试着测试一下随机mathe
代码假设Fans给出的目标数据就是按0,1,2,...,N-1顺序给出（但是mathe不知道）
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#ifndef N
#define N 20
#endif
#define TC 8
#define TARGET 1
struct Data{
char v;
int c;
};
std::vector<Data> usedlist;
std::vector<Data> leftlist;
char leftc;
char avail;
double tvalue;
double ve;
void init()
{
tvalue = log(2*M_PI*N)/2+N*(log(N)-1)-log(TARGET);
ve=exp(-1.0);
int i,j;
leftc=N;
for(i=0;i<N;i++){
for(j=0;j<N;j++)avail=j;
}
}
void dumpleft()
{
int i;
int j;
for(i=0;i<leftlist.size();i++){
printf("\n");
for(j=0;j<N;j++)printf("%d ",leftlist.v);
}
printf("\n");
}
char used;
char mc;
char umc;
Data tryv;
int depth;
void search()
{
if(depth>=N){
leftlist.push_back(tryv);
return;
}
int i,j;
for(i=0;i<usedlist.size();i++){
if(mc>usedlist.c||umc>N-usedlist.c)return;
}
for(i=0;i<leftc;i++){
int k = avail;
if(used==0){//The value has not been used, try use it
used=1; tryv.v=k;if(k==depth)tryv.c++;
for(j=0;j<usedlist.size();j++){
if(usedlist.v==k){
mc++;
}else{
umc++;
}
}
depth++;
search();
depth--;
for(j=0;j<usedlist.size();j++){
if(usedlist.v==k){
mc--;
}else{
umc--;
}
}
used=0;if(k==depth)tryv.c--;
}
}
}
void collect_lefts()
{
depth=0;
tryv.c=0;
memset(used,0,sizeof(used));
memset(mc,0,sizeof(mc));
memset(umc,0,sizeof(umc));
search();
}
int trygenrand(Data& d)
{
char cused;
memset(cused,0,sizeof(cused));
int i,j,k;
d.c=0;
for(i=0;i<N;i++){
j=rand()%leftc;
int choice=-1;
for(k=j;k<leftc;k++){
if(cused]==0){choice=k;break;}
}
if(choice<0){
for(k=0;k<j;k++){
if(cused]==0){choice=k;break;}
}
}
if(choice<0)return -1;
cused]=1;
d.v=avail;
if(d.v==i)d.c++;
}
return 0;
}
void genrand(Data& d)
{
while(trygenrand(d)<0);
int i,j;
usedlist.push_back(d);
if(d.c==0){
for(i=0;i<N;i++){
for(j=0;j<leftc;j++){
if(d.v==avail)break;
}
if(j>=leftc){
fprintf(stderr,"Internal error\n");
exit(-1);
}
for(;j<leftc-1;j++){
avail=avail;
}
}
leftc--;
}
double dd=ve;for(i=0;i<d.c;i++)dd/=(i+1);
tvalue+=log(dd);
}
int main()
{
Data d;
srand(time(NULL));
init();
int t=0;
while(leftc>TC){
genrand(d);
t++;
}
printf("try %d times to reach small probability, leftc = %d\n", t, leftc);
collect_lefts();
printf("Total %d left\n", (int)leftlist.size());
dumpleft();
}
测试了含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远远不够。
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#ifndef N
#define N 12
#endif
#define MINTC 3
#define TC 6
#define TARGET 5
struct Data{
char v;
int c;
bool operator==(const Data& d)const{
int i; for(i=0;i<N;i++)if(v!=d.v)return false;
return true;
}
};
std::vector<Data> usedlist;
std::vector<Data> leftlist;
char leftc;
char avail;
double tvalue;
double ve;
void init()
{
tvalue = log(2*M_PI*N)/2+N*(log(N)-1)-log(TARGET);
ve=exp(-1.0);
int i,j;
leftc=N;
for(i=0;i<N;i++){
for(j=0;j<N;j++)avail=j;
}
}
void filter(const Data& d)
{
int i,j;
std::vector<bool> valid;
valid.resize(leftlist.size());
for(i=0;i<valid.size();i++)valid=true;
for(i=0;i<leftlist.size();i++){
int c=0;
for(j=0;j<N;j++)if(d.v==leftlist.v)c++;
if(c!=d.c)valid=false;
}
for(i=0,j=0;i<leftlist.size();i++){
if(valid){
if(i>j)leftlist=leftlist;
j++;
}
}
leftlist.resize(j);
}
void getMaxDist(Data& d)
{
int i,j;
int c;
int used;d.c=0;
for(i=0;i<N;i++)used=0;
for(i=0;i<N;i++){
memset(c,0,sizeof(c));
for(j=0;j<leftlist.size();j++){
c.v]++;
}
int short_dist = 2*N+1, select=-1;
for(j=0;j<N;j++){
int v=2*c-leftlist.size();
if(v<0)v=-v;
if(v<short_dist&&used==0){
short_dist=v;select=j;
}
}
if(select>=0){
used=1; d.v=select;if(i==select)d.c++;
}else d.v=-1;
}
for(i=0,j=0;i<N;i++){
if(d.v<0){
for(;j<N;j++){
if(used==0){
used=1;d.v=j;if(i==j)d.c++;break;
}
}
}
}
do{
for(i=0;i<usedlist.size();i++){
if(d==usedlist){
break;
}
}
if(i==usedlist.size())return;
//If it has been used, randomly swap any two items
int s=rand()%N; int t=rand()%(N-1); if(t>=s)t++;
int tmp=d.v;d.v=d.v;d.v=tmp;d.c=0;
for(i=0;i<N;i++)if(d.v==i)d.c++;
}while(1);
}
void output(const Data& d)
{
int i;
for(i=0;i<N;i++){
printf("%d ",d.v);
}
printf("\n");
}
void dumpleft()
{
int i;
int j;
for(i=0;i<leftlist.size();i++){
printf("\n");
for(j=0;j<N;j++)printf("%d ",leftlist.v);
}
printf("\n");
}
char used;
char mc;
char umc;
Data tryv;
int depth;
int countlimit;
int search()
{
if(depth>=N){
leftlist.push_back(tryv);
if(leftlist.size()>countlimit)
return -1;
else return 0;
}
int i,j;
for(i=0;i<usedlist.size();i++){
if(mc>usedlist.c||umc>N-usedlist.c)return 0;
}
for(i=0;i<leftc;i++){
int k = avail;
if(used==0){//The value has not been used, try use it
used=1; tryv.v=k;if(k==depth)tryv.c++;
for(j=0;j<usedlist.size();j++){
if(usedlist.v==k){
mc++;
}else{
umc++;
}
}
depth++;
if(search()<0)return -1;
depth--;
for(j=0;j<usedlist.size();j++){
if(usedlist.v==k){
mc--;
}else{
umc--;
}
}
used=0;if(k==depth)tryv.c--;
}
}
return 0;
}
int collect_lefts(int limit)
{
depth=0;
tryv.c=0;
memset(used,0,sizeof(used));
memset(mc,0,sizeof(mc));
memset(umc,0,sizeof(umc));
leftlist.clear();
countlimit=limit;
return search();
}
int trygenrand(Data& d)
{
char cused;
memset(cused,0,sizeof(cused));
int i,j,k;
d.c=0;
for(i=0;i<N;i++){
j=rand()%leftc;
int choice=-1;
for(k=j;k<leftc;k++){
if(cused]==0){choice=k;break;}
}
if(choice<0){
for(k=0;k<j;k++){
if(cused]==0){choice=k;break;}
}
}
if(choice<0)return -1;
cused]=1;
d.v=avail;
if(d.v==i)d.c++;
}
return 0;
}
void genrand(Data& d)
{
while(trygenrand(d)<0);
int i,j;
usedlist.push_back(d);
if(d.c==0){
for(i=0;i<N;i++){
for(j=0;j<leftc;j++){
if(d.v==avail)break;
}
if(j>=leftc){
fprintf(stderr,"Internal error\n");
exit(-1);
}
for(;j<leftc-1;j++){
avail=avail;
}
}
leftc--;
}
double dd=ve;for(i=0;i<d.c;i++)dd/=(i+1);
tvalue+=log(dd);
}
int main()
{
Data d;
srand(time(NULL));
init();
int t=0;
while(t<N*N){
genrand(d);
t++;
if(t>=MINTC){
if(collect_lefts(100)>=0)break;
}
}
printf("try %d times to reach small probability, leftc = %d\n", t, leftc);
if(t>=N*N)
collect_lefts(100);
printf("Total %d left\n", (int)leftlist.size());
dumpleft();
while(leftlist.size()>1){
getMaxDist(d);
printf("Use: ");output(d);
usedlist.push_back(d);
filter(d);t++;
}
printf("Total tried %d times\n",t);
}
试验了上面的代码，先随机，减少到一定程度，就用贪心法选择看上去还行的方法，实验结果基本上在2N次以内解决。但是N不能太大，不然程序运行时间会很长。其中参数TC建议选择接近N/2,越小代码跑得越快，但是前面随机使用次数会越多。而参数MINTC表示前面这么多次必然全随机，不会探测是否需要切换到贪心法