请教个算法问题，给点建议

[sorry]

每一位上范围是1~30整数，生成13位组合数列

要求：

（1）每一位不重复（1,1,....不合格）
（2）连续位数不大于5（如：1,2,3,4,5,6 ......即不合格）；
（3）相邻两位数差不大于5


比如：1,2,3,4,6,7,8,9,11,12,13,14,16 即合格

组合数量特别多，用循环一个个检测速度太慢了，请教大家还有什么建议吗？先谢谢了！ ;)

[ianluo]

30个数放到数组里然后用rand()%30来取随机坐标，然后碰到相同或者与前一位超过5的话重取，满13个为止，应该满足需求吧。

[lijinma]

@ianluo 随机取完你再排序？ 不排序无法判断连续位数不大于5，划不来；

[ls2110609]

你需要检测还是生成 检测可能可以压缩进一个数据类型内进行

[cassyfar]

题目写得都不清楚。
生成的数列是sorted还是unsorted的，你是要检测还是要生成啊？如果是检测的话算法最好的也是O(n)了 你指的用循环检测到底是指怎么用循环检测啊？

[casparchen]

这难道不是一个简单dfs么

[casparchen]

写了段代码来跑，包含1的就有5908962个。。。

[neoz]

<code>
#include<iostream>
#include<random>
#include<time.h>
using namespace std;
int rpc(int x[13],int xx,int ra)
{
if(xx>5)
{
if((ra-x[xx-1]==1)&&(x[xx-1]-x[xx-2]==1)&&(x[xx-2]-x[xx-3]==1)&&(x[xx-3]-x[xx-4]==1)&&(x[xx-4]-x[xx-5]==1))
return 1;
else
return 0;
}
return 0;
}
int main()
{
clock_t start_time=clock();
int count=0;
for(int j=0;j<10000;j++)
{
//random_device rd;
srand( (unsigned)time( NULL ) );
bool repeat[31]={0};
int x[13]={0};
int r=rand()%30+1;
x[0]=r;
repeat[r]=1;
for(int i=1;i<13;i++)
{
int ran=rand()%30+1;
while(repeat[ran]==0)
{
ran=rand()%30+1;
count++;
}
if(abs(ran-x[i-1])>5 || rpc(x,i,ran))
{
i--;
}
else
{
x[i]=ran;
repeat[ran]=1;
}
}
//cout<<j<<"--";
//for(int i=0;i<13;i++)
//cout<<x[i]<<" ";
//cout<<endl;
}
clock_t end_time=clock();
cout<< "Running time is: "<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000<<"ms"<<endl;//输出运行时间
cout<<"The count of ceash is: "<<count<<endl;
return 0;
}
</code>
测了下是15-25ms之间。用未排序下去做。。。c++初学者。。。不会位运算，第一次想别人的问题，第一次贴出代码。还需努力，见笑了。。。

[casparchen]

全部有18637773个

[casparchen]

https://gist.github.com/a6daaedabf97d3b9171e.git

[casparchen]

怎么插入gist
http://gist.github.com/anonymous/a6daaedabf97d3b9171e

[sorry]

@ianluo 这样会遗漏很多。


@cassyfar 生成的是排过序的


@casparchen 特别感谢！昨天夜里实现了下，用树做剪枝，动态规划的思想。效率在两分钟内搞定。如果循环的话，组合量是13的30次方，量太大，没法算。。。

[belin520]

@casparchen 加script标签

[dingyaguang117]

=。= 是啊 就是一个DFS啊