一个来自实践的算法难题(300分)

我没证明，也想了好久这个差序列的排列问题（我只考虑相邻两数的差组成的序列）。
这个序列要满足条件就是任意子序列的和不在该序列中且，任意两个的和不同。
序列和+1就是最大数的值，用遍历的办法应该是可以得到解的，但效率肯定很低。
现在就是要得到差序列冗余的规律就好办了
兄弟努力！

DarwinZhang:
从已知结果来看，Min(an) >＝ (n-1)*n/2 + [n/5]对提高速度不会有大的帮助，实际上,
当n较大时，其左边远大于右边。但它的证明应该很困难，我对你的证明很感兴趣，还是
贴出来吧。
已经发现有Min(a[n])>=Min(a[n-1])+n。但我不能证明。
lldhz:
　　你是对的。遍历的方法虽然很效率低，但也许是唯一的方法。我们致力于找出一些
规律，减少搜索空间。

排列组合的方法肯定不可行，我也偿试过了。
可能还是要从递推或递归的角度进行。
一般来说，这N个数的间距的大小肯定是相隔 或小的分布在两头。
总之间距的大小是比较“乱”的。要解的就是这个“乱”。
以下是考察间距的情况，先定义为“级差”：
其实 n 个数的两两差就是这个级差（N-1个数）的连续和。
连续的 1 个 2 个 n-1 个数的和。
n-1 个数的和不用考察，最大距离只有一个。

1 3 4
>> 2 1
连续和为 2,1, 3 没有重复，不可能有比它再优的解
1 3 6 7
>> 2 3 1
连续和为 2,3,1, 5,4 ,6 没有重复，不可能有比它再优的解
1 3 8 11 12
>> 2 5 3 1
连续和为 2,5,3,1, 7,8,4 10,9 11 没有重复

为什么 1 2 3 4 不行，不管怎么排列，肯定会有连续的两数的和等于另外一个
1 2 3 4 1+2=3
1 3 2 4 1+3=4
1 4 2 3 1+4=2+3
1 6 8 14 17 18
5 2 6 3 1 也没有 4 2+4=6
6 换成 4 ，或 5 换成 4都不行
1 3 8 16 22 25 26
2 5 8 6 3 1 >> 4,7
2+4=6
2+5=7
1 3 13 20 26 31 34 35
2 10 7 6 5 3 1 >>4,8,9
1+3=4
5+3=8
2+9=6+5
1 4 10 18 20 33 40 44 45
3 6 8 2 13 7 4 1 >> 5 9 10 11 12
4+1=5
3+6=9
8+2=10
7+4=11
6+8=2+12
总而言之！！！！！！！！
我们要研究的是：
从 1,2,3,4,5,....,m 中取一个非重复的n排列(m>=n)：这个排列的连续和不等 并且和最小。
当n 已知时，我们可以给出 m 的范围
现在有价值的结论和感觉是：
(1) m 的范围为 [n..2^(n-1)] ，这一条比较容易，应该可能确认。
(2) 1 肯定在这个系列中？？？？？如果没错的话。这一条最重要，不引人注目。
可能还能推出其它的！！！！！！有人能证明吗？？？？

我能举出反例来否定它，如 2 3 4 >> 1 2 3
但 1 2 3 不能成为最优解，是困为 2 3 4 本身不是最优解。
(3) 1 2 作为一个组合肯定不能和 3 并存。还有 (2 3 )和 5
如序列中包含以下子序列，这个序列肯定无效：
（1 2）...... 3
（2 1）.......3
3......（1 2）
3 ......（2 1）
(1 3 2)......6
6........(1 3 2)
其实这是“这个排列的连续和不等”的推论！！！！！！！

一个两次的第归函数

jsxjd:
如果我们能证明最优解中，一定存在两个相差1的数。那么我们在证明过程中所发现
的规律，将使我们向前迈一大步。
　　我还有个想法：就是对一个差值序列，经过若干步调整（交换、增加、减少），可
以得到一个解序列。如果我们能找出调整方法，也许就能最终解决这个问题。

我根据3..16的已知数据进行了曲线拟合，用泊松分布曲线，公式为:
y=Exp(a)*Power(x,b)
计算出a=-1.302;
b=2.335。
x y
5 11.659
10 58.823
15 151.608
16 176.226
17 203.070
20 296.793
30 764.939
34 1024.594
35 1096.346
36 1170.887 //*************
37 1248.224
尽管曲线拟合是有误差的，但我估计当N=36时，最优解不会小于1096——这是不是可以
说明intfree兄得到的1149已经足够理想了呢？（误差为4.8%）——您已经在非常短的时间
内得到了95%以上满意的解。
我的观点和温柔一刀一致——就算你可以开发出更好的算法，1秒就可以算出N=17的最优
值，计算N=36没有几年的时间也还是下不来的（我指的是算法仍然采用穷举法的思路的情况
下）。

也许我们不能最终攻克这个难题，但在攻克的过程中，我们会得到很多。

很简单

参与

1,2都肯定是在某个可行解的差序列当中的！
因为差序列要满足条件就是任意子序列的和不在该序列中且任意两个的和不同
没有子序列能把1，2给淘汰掉！
至于是不是在最优解当中，有待证明（比较困难，因为可能存在多个最优解）
还有观察现有的数据：
好象可以得到：1..[n/3]都是在解的差序列当中的！
但是有一个问题：差序列中没个数的位置都是不确定的，位置的变化也影响着最后结果
的变化，确认差序列的部分元素对总个序列的求解帮助会很大吗？？
我觉得现在最重要的是确定差中最大的一个的大小范围。那样的话可以把问题变成：
求一个序列，序列要满足条件就是任意子序列的和不在该序列中且任意两个的和不同。
这样可以减少一个循环的计算。

转自CSDN，By gauss(Powered-by-Internet) :
今天碰巧看到这个网页 http://www.distributed.net/ogr/index.html.en
想起前端时间论坛大家讨论过类似问题，发现原来早就有人做过。翻翻CSDN的旧帖，好像还没有人提到过这点。
原来这个问题叫做Optimal Golomb Rulers，上面提到的网页说得很仔细，还有很多link和article，我也来不及仔细看了，先给大家说一声，希望有点启示。
Reference那里最早的文章是
WB - Wallace C. Babcock
W. C. Babcock, "Intermodulation Interference in Radio Systems", Bell System Technical Journal, 1953, p. 63-73.
果然是通信频率分配模型
有人正在用分布式计算的方法来求N＝24的最优解，25也开始了。
下面是已知最优的结果，原来是从0开始的，我转换了一下，发现前面的和大家算的结果一致，只是有些序列位置是对称的。
（来自 http://www.research.ibm.com/people/s/shearer/grtab.htm）
N，序列
1, 1
2, 1 2
3, 1 2 4
4, 1 2 5 7
5, 1 2 5 10 12
5, 1 4 5 10 12
6, 1 2 5 11 13 18
6, 1 2 5 11 16 18
6, 1 4 6 10 17 18
6, 1 5 7 10 17 18
7, 1 2 5 11 19 24 26
7, 1 3 4 11 17 22 26
7, 1 3 7 10 15 25 26
7, 1 2 8 12 21 24 26
7, 1 4 5 13 19 24 26
8, 1 2 5 10 16 23 33 35
9, 1 4 10 18 20 33 40 44 45
10, 1 2 7 11 24 27 35 42 54 56
11, 1 2 5 14 29 34 48 55 65 71 73
11, 1 2 10 20 25 32 53 57 59 70 73
12, 1 3 7 25 30 41 44 56 69 76 77 86
13, 1 8 9 18 22 37 48 64 70 82 102 105 107
14, 1 6 29 39 42 50 51 69 76 93 108 122 124 128
15, 1 7 8 16 29 41 52 76 90 93 95 122 132 148 152
16, 1 2 5 12 27 33 57 69 77 116 118 135 151 164 169 178
17, 1 6 8 18 53 57 68 81 82 101 123 139 160 166 169 192 200
18, 1 3 11 23 54 57 83 84 90 99 131 149 154 168 189 193 206 217
19, 1 5 14 16 43 57 60 78 94 117 127 139 147 175 215 222 241 246 247
20, 1 25 31 44 56 72 76 90 105 126 128 163 168 190 207 216 273 276 283 284
21, 1 5 24 38 41 49 69 79 139 148 155 190 205 239 251 252 257 278 310 332 334
22, 1 2 10 15 44 71 107 123 125 129 160 180 205 224 254 264 271 292 331 342 354 357
23, 1 7 23 25 44 57 96 127 138 147 173 174 202 214 259 274 282 307 312 356 366 370 373

在那堆网页里面也找到一个N＝36的，但不知是否最优（0开始）
0 18 20 42 54 128 137 145 178 271
301 328 332 353 367 412 413 483 502 551
580 623 649 655 728 743 756 820 843 887
942 949 952 989 1000 1005

1 6 8 14 17 18
5 2 6 3 1
7 8 9 4
13 11 10
16 12
17
最上面一行是N=6的时候的最优解
下面的是差值
我们可以看到17=12+15=16+1=13+4=10+7......
当N=n时我们测试m是否为Nn的算法变为
将m-1...1填入差值的倒三角矩阵，满足以上的差值规律
由于差值限制性很强，我觉得能提高计算m是否为最优值的速度。
同时差值排列出来就等于整个序列也出来了。
希望我写的这些东西能有点用途。^o^

我和一个学物理的朋友谈起这件事情，他觉得可以利用泡利不相容原理来解决。
他设计的理想试验，据说可以一瞬间算出来。我也听得半懂不懂得，见笑了。[]

1）差值的个数是：n*(n-1)/2
2)a[n]>=n*(n-1)/2 + 1;
以上两条大家都说了
3)a[n]/(n*(n-1)/2)的范围，根据1--22的那个表，可以算出在1--1.7之间
我的想法是求一个近似解
a)估计一个近似的 a[n] = int(0.5*n*(n-1)*1.5);
b)设定有关集合，并作初始化；
c)用随机的办法，构造出n*(n-1)/2个不同差值，最小的是1，最大的是a[n]-1;
d)根据差值构造一个近似解，根据解序列中不能有相同的数，检查界序列的合法性，合法则继续，否则回到c);
e)把a[n]和上一次的a[n]比较，取较小者，回到c)；
f)根据人为规定的上面的循环次数，做出有误解的判断，如果有解，减小a[n],回到c),如果无解，增加a[n],回到c)
g)输出解
4）对于f)，根据试验确定循环次数的大小，如果循环次数必须取非常大的数，说明方法不可行，如果用pascal的集合，a[n]最大不能超过255，也就是n < 20，使用C++的STL的set可能方便些
我没有写代码，我先试一试，可以的话，再贴出来

n = 7，这一组也是
1 3 8 14 22 23 26

to kusanagi
我实现了一个，思路和你相似，可以在瞬间（TickCount之差为0...）检测出一个数列是否符合要求，但是现在的问题是，生成这样一个数列不太容易，工作量比较大。
在n=16的情况下要生成一个16/39的排列，所以这种方式下的计算量仍然不小。