完美间隔配对排列

aimisiyou

王守恩 发表于 2020-3-2 12:47
找这样的 B 也可以，B=首尾没有0，中间必须有0，不去重。
1, 1, 2, 4, 11, 38, 156, 788,.......=B/2+A0 ...

无论添加什么其他限定规则，你都得先找到无其他限制规则情况下的所有结果（即2个1之间有1个数，2个2之间由个数……）。再根据限制规则去掉不符合要求的，剩下的就是符合你所限定规定要求的数目。我在意的是前面的结果。你都能找到1到100，难道还不能找到其中的所有奇数，所有偶数，所有3的倍数……

aimisiyou

猜想f(n)=(1/2)*((2*n+1)!-q(n)* （2*n-1）!+q(n^3)*(2*n-3)！-q(n^5)*(2*n-5)！+…)的形式。
其中q(n^k)表示一个不超过k次的多项式。

aimisiyou

从中午跑到现在，得出f（11）=320208.（无首尾比较规则）。不敢再往下跑了！！！
求f(10) 按30分钟计算，求f(11)所花时间理论上为30分钟*22*23=4.2小时，与实际6小时左右偏差不多。
按此估计求f(12)理论时间6小时*24*25=150天=5个月！！！

aimisiyou

王守恩 发表于 2020-3-3 12:09
小结。
将 0,1,1,2,2,…,n,n 排成一列，要求两个 k 中间有 k 个数（k=1,2,…,n)，有几种排法？
通项 ...

要找其中一个答案，可以随机选取其中一个分支往下找，每次随机选择一个分支往下。要碰运气，可能碰上死胡同。

aimisiyou

dlpg070 发表于 2020-3-1 09:54
我的搜索法较笨,n大时很慢,结果直接存盘,得数列:
1, 1, 2, 4, 11, 38, 156,  788,  4158,  23384        ...

检验了下你的猜想，N>5时,0不可能出现在首尾。猜想是错误的。
n= 5时不存在
n= 6时不存在
n= 7时存在0出现在首尾的情况。
("027423564371516" "274235643715160" "072452634753161" "724526347531610" "074151643752362" "741516437523620" "071316435724625" "713164357246250" "071416354732652" "714163547326520" "017125623475364" "171256234753640" "057141653472362" "571416534723620" "073161345726425" "731613457264250" "017126425374635" "171264253746350" "072462354736151" "724623547361510" "024723645317165" "247236453171650" "057236253471614" "572362534716140" "035723625417164" "357236254171640" "057416154372632" "574161543726320" "035743625427161" "357436254271610" "052732653417164" "527326534171640" "015173465324726" "151734653247260" "072632453764151" "726324537641510" "037463254276151" "374632542761510" "041716425327635" "417164253276350" "073625324765141" "736253247651410" "023726351417654" "237263514176540" "057263254376141" "572632543761410" "034573641512762" "345736415127620" "051716254237643" "517162542376430" "052472654131763" "524726541317630" "036713145627425" "367131456274250" "034673245261715" "346732452617150" "026721514637543" "267215146375430" "014167345236275" "141673452362750" "045671415362732" "456714153627320" "014156742352637" "141567423526370" "053672352461714" "536723524617140" "015167245236473" "151672452364730" "015146735423627" "151467354236270" "062742356437151" "627423564371510" "046171435623725" "461714356237250" "016172452634753" "161724526347530" "023627345161475" "236273451614750" "046171452632753" "461714526327530" "041617435263275" "416174352632750" "056171354632742" "561713546327420" "015163745326427" "151637453264270" "053647352462171" "536473524621710" "052462754316137" "524627543161370" "026327435614175" "263274356141750" "046357432652171" "463574326521710" "025623745361417" "256237453614170" "052642753461317" "526427534613170" "026325734615147" "263257346151470" "016135743625427" "161357436254270" "061517346532472" "615173465324720")
_

aimisiyou

顺带做下N皇后问题吧(也是爆炸增长问题)，即在N*N的棋盘上放置N个皇后(N>1)，使得任意两个皇后都不存在攻击状态（即不能同行同列同斜45度线上），求所有可能存在的状态及状态个数。总个数用f(n)表示。
N=2,f(2)=0;
N=3 ,f(3)=0;
N=4，f(4)=2;
……

aimisiyou

顺带也解决了N皇后问题（与此题一样，都是多叉树裁枝查找过程，运算量都是爆炸式增长）。
_ (h 4)
((3 1 4 2) (2 4 1 3))
_ (h 5)
((1 3 5 2 4) (1 4 2 5 3) (2 4 1 3 5) (2 5 3 1 4) (3 1 4 2 5) (3 5 2 4 1) (4 1 3 5 2) (4 2 5 3 1) (5 2 4 1 3) (5 3 1 4 2))
_ (h 6)
((5 3 1 6 4 2) (4 1 5 2 6 3) (3 6 2 5 1 4) (2 4 6 1 3 5))
_ (h 7)
((1 3 5 7 2 4 6) (1 4 7 3 6 2 5) (1 5 2 6 3 7 4) (1 6 4 2 7 5 3) (2 4 6 1 3 5 7) (2 4 1 7 5 3 6) (2 5 7 4 1 3 6) (2 5 3 1 7 4 6) (2 5 1 4 7 3 6) (2 6 3 7 4 1 5) (2 7 5 3 1 6 4) (3 1 6 2 5 7 4) (3 1 6 4 2 7 5) (3 5 7 2 4 6 1) (3 6 2 5 1 4 7) (3 7 4 1 5 2 6) (3 7 2 4 6 1 5) (4 1 5 2 6 3 7) (4 1 3 6 2 7 5) (4 2 7 5 3 1 6) (4 6 1 3 5 7 2) (4 7 5 2 6 1 3) (4 7 3 6 2 5 1) (5 1 6 4 2 7 3) (5 1 4 7 3 6 2) (5 2 6 3 7 4 1) (5 3 1 6 4 2 7) (5 7 2 4 6 1 3) (5 7 2 6 3 1 4) (6 1 3 5 7 2 4) (6 2 5 1 4 7 3) (6 3 7 4 1 5 2) (6 3 5 7 1 4 2) (6 3 1 4 7 5 2) (6 4 7 1 3 5 2) (6 4 2 7 5 3 1) (7 2 4 6 1 3 5) (7 3 6 2 5 1 4) (7 4 1 5 2 6 3) (7 5 3 1 6 4 2))

_ (length (h 4))
2
_ (length (h 5))
10
_ (length (h 6))
4
_ (length (h 7))
40
_ (length (h 8))
92
_ (length (h 9))
352
_ (length (h 10))
724

aimisiyou

可以发现总个数变化不是指数增长，大约是递增乘以一个数值。虽然搜索的范围是爆炸式的，但总个数增长大约是阶乘的模式。估计f(20)<20!（可以肯定的是f(20)<41!）
对于只求满足要求的总个数，换个思路有些进展，尝试求出f(12)。
如果能求出来f(12)，f(20)也就不是问题了。

dlpg070

aimisiyou 发表于 2020-3-4 13:14
可以发现总个数变化不是指数增长，大约是递增乘以一个数值。虽然搜索的范围是爆炸式的，但总个数增长大约是 ...

代码进行一些优化,速度大幅提高,我的计算结果:
1 和aimisiyou相同 n=1,---,11
2 速度快一些
3 预计 n=12 计算时间不会太长,约6664*20= 133280秒= 37.0小时
  如果采用多线程,分段多人协作等,几个小时内可得结果
4 考虑到 aimisiyou 采用先进算法,理应比我快,请LISP转c++ 试试
5 n=20 难,我望而却步,如得解,可发论文,可申请OEIS数列号,祝好运

*** 王守恩一个好玩的游戏搜索 ***
    Wed Mar  4 10:21:21 2020

n=  8 cnt=1876  Elapsed time 0.59

n=  9 cnt=8316  Elapsed time 13.86   = 0.59   * 21.5

n= 10 cnt=46768 Elapsed time 389.75  = 13.86  * 28.1

n= 11 cnt=320208 Elapsed time 6664.78 = 389.75* 17.1


-------
-------------------------
屏幕显示:防死机,演示分段处理
n=11 20 段
n=12 22 段

L:\Release>game
ctime is Wed Mar  4 10:21:21 2020

n=11
n=11
n= 11 i1=  0 Elapsed time 0.01
n= 11 i1=  1 Elapsed time 246.00
n= 11 i1=  2 Elapsed time 491.56
n= 11 i1=  3 Elapsed time 734.86
n= 11 i1=  4 Elapsed time 976.42
n= 11 i1=  5 Elapsed time 1216.60
n= 11 i1=  6 Elapsed time 1458.84
n= 11 i1=  7 Elapsed time 1702.57
n= 11 i1=  8 Elapsed time 1946.33
n= 11 i1=  9 Elapsed time 2189.68
n= 11 i1= 10 Elapsed time 2433.57
n= 11 i1= 11 Elapsed time 2678.44
n= 11 i1= 12 Elapsed time 2945.66
n= 11 i1= 13 Elapsed time 3236.90
n= 11 i1= 14 Elapsed time 3546.96
n= 11 i1= 15 Elapsed time 3881.42
n= 11 i1= 16 Elapsed time 4245.66
n= 11 i1= 17 Elapsed time 4642.54
n= 11 i1= 18 Elapsed time 5079.83
n= 11 i1= 19 Elapsed time 5563.39
n= 11 i1= 20 Elapsed time 6089.63

Elapsed time 6664.78

aimisiyou

可以推出f(12)<C(192,12).
已经找到F(n)一种计数方式，但涉及到大数运算，目前只能给出一些推论，小于某一个上界。
如果大数运算解决了，统计个数f(n)的复杂度为O(n)（若将大数运算看成平常数运算的话）.