完美间隔配对排列

王守恩

问题：将 0,1,1,2,2,…,n,n 排成一列，使得两个 k 中间有 k 个数（k=1,2,…,n), 称为一个完美间隔配对排列。
一个完美间隔配对排列的逆排列显然也是完美间隔配对排列，两者视为等价，我们取其首＜尾的作代表。
记符合要求的全部完美间隔配对排列数为a(n)，手工排得前几个答案如下：
a(1)=1： 101
a(2)=1 :  12102
a(3)=1： 1312032
a(4)=3： 131423024, 141302432, 240231413

不知道结果是否正确，期待往后搜索更多结果，或许可以得到一个新的序列。

王守恩

补充几句。
1、此题三十年前很流行，几乎每个小朋友都在做。遗憾的是，不是每对数都有答案，
本人在此基础上加了 1 个 0，能使每对数都有答案，可以连续做题目了。
2、做题目最好的方法是动手，希望来做这道题的网友，享受每次找到答案时的喜悦，
更在意信任自己一定能找到答案的信念，因为探索比结果更诱人。
3、向三十年前的老朋友：继承、方运加、刘京友、单墫.....，见过面与未见过面的，
我想你们！可好？还记得躲在教室角落里的我？

dlpg070

我想改为摆扑克牌游戏或2支比赛队混合排座次等可能更有趣
下面是我的计算结果,
n=4的结果与楼主不同(多一个解)

n= 1
[ 1]  1, 0, 1,
Elapsed time 0.00

n= 2
[ 1], 1, 2, 1, 0, 2,
Elapsed time 0.00

n= 3
[ 1]  1, 3, 1, 2, 0, 3, 2,
[ 2]  0, 2, 3, 1, 2, 1, 3,
Elapsed time 0.00

n= 4
[ 1]  1, 3, 1, 4, 2, 3, 0, 2, 4,
[ 2]  1, 4, 1, 3, 0, 2, 4, 3, 2,
[ 3]  2, 4, 0, 2, 3, 1, 4, 1, 3,
[ 4]  0, 2, 3, 4, 2, 1, 3, 1, 4,
Elapsed time 0.00

aimisiyou

其实就是多叉树裁枝查找过程，符合条件的继续往下分枝。可以编程序找到所有解。
核心问题是k****k如何插入到a*b**c***c**b***a中，且K不能落在有数字的位置上。
如2**2插入到3**435**4**5中去的结果有2**23**435**4**5，2*32*435**4**5，3**4352*42*5，3**435*24*25，3**435**4*252，3**435**4**52**2.
可以看成在3**435**4**5前后均加上4个*, 即得****3**435**4**5****, 然后匹配连续四个字符,如果四个字符首尾都是*, 则可将2**2替换插入，得到所有的结果。

dlpg070

aimisiyou 发表于 2020-2-29 14:46
其实就是多叉树裁枝查找过程，符合条件的继续往下分枝。可以编程序找到所有解。核心问题是k****k如何插入到 ...

我已经搜索到n=9,但因为缺少理论支撑,不知是否有遗漏,不敢贴出,
我初步判断,我得到解是对的,可能有遗漏,但不可能有错.
我的结果显示这个数列没有被OEIS收录.
不妨贴出你的具体结果,我们讨论一下,互相印证.

aimisiyou

(defun ff (n)
(defun f (k)
  (setq str "")
  (repeat k
    (setq str (strcat "*" str))
   )
)
(setq str_n (strcat (itoa n) (f n) (itoa n)) strlst (list str_n) num (+ n n 1))
(while (> n 1)
   (setq vlst nil j 0 nk (length strlst))
   (while (< j nk)
       (setq en (nth j strlst))
       (setq str_n (strcat (f (+ n 1)) en (f (+ n 1))))
           (setq i 1)
           (while (< i (+ (strlen en) n 2))
              (if (= "*" (substr str_n i 1) (substr str_n (+ i n) 1))
                      (if (= i 1)
                             (progn
                     (setq str_new (strcat (itoa  (- n 1)) (substr str_n (+ i 1) (- n 1)) (itoa (- n 1)) (substr str_n (+ n 2))))
                                         (setq str_new (vl-string-right-trim "*" (vl-string-left-trim "*" str_new)))
                                         (if (<= (strlen str_new) num)
                         (setq vlst (cons str_new vlst))
                                          )
                              )
                         (progn
                     (setq str_new  (strcat (substr str_n 1 (- i 1)) (itoa (- n 1)) (substr str_n (+ i 1) (- n 1))
                           (itoa (- n 1))  (substr str_n (+ n i 1))))
                     (setq str_new (vl-string-right-trim "*" (vl-string-left-trim "*" str_new)))
                     (if (<= (strlen str_new) num)
                         (setq vlst (cons str_new vlst))
                                          )
                              )
                       )
                        )
                    (setq i (+ i 1))
             )
           (setq j (+ 1 j))
        )
     (setq strlst vlst)
         (setq n (- n 1))
  )
  (setq vvlst (mapcar '(lambda (x) (vl-string-translate "*" "0" x)) strlst))
)
FF
_ (ff 1)
("101")
_ (ff 2)
("20121" "12102")
_ (ff 3)
("2302131" "231213" "312132" "1312032")
_ (ff 4)
("240231413" "420324131" "41312432" "141302432" "234203141" "23421314" "131423024" "314132042")
_(ff 5)
("42352430151" "40352432151" "14135243205" "42502431513" "41512432503" "20425314135" "14153042352" "23425314105" "34253240151" "34513142502" "13145320425" "52402354131" "20524131543" "15104235243" "50141352432" "25324035141" "53141352402" "30523421514" "31513420524" "50234253141" "15123425304" "15103425324")
_ (ff 6)
("6014153642352" "6234253640151" "2612145360435" "4260245316135" "4161345236205" "4263245316105" "6420524631513" "3642352460151" "3640352462151" "2632453064151" "3161345026425" "6121524630543" "2612153460354" "2462354036151" "3046325421615" "1016425324635" "1316435024625" "1613504362542" "3062352416154" "6025324635141" "1612532463504" "2632503461514" "1416254230653" "2042635413165" "1416354032652" "2342635410165" "2462514136503" "1014635243265" "1314635240265" "3046351412652" "2062514136543" "1016352432654" "2362531416504" "3625324065141" "6250234653141" "1413564320526" "1415604235263" "4056141352632" "1014562342536" "3456314152602" "2562141536403" "5620425364131" "1015623425364" "3056314152642" "5610145362432" "2562304536141" "5613145362402" "3560324526141" "4151643052362" "4053642352161" "1415364235206" "4516142532603" "2452634053161" "5264205346131" "1015364235246" "5161245236403" "1516304532642" "4530643512162" "3450364251216" "5246205431613" "1514603542362" "1512642530463" "1510642532463" "3151364250246" "5016135423624" "5026325431614" "5316135420624" "5340635412162" "1510463524326" "2532463514106")
_

aimisiyou

_ (length (ff 1))
1
_ (length (ff 2))
2
_ (length (ff 3))
4
_ (length (ff 4))
8
_ (length (ff 5))
22
_ (length (ff 6))
70
_ (length (ff 7))
312
_(length (ff 8))
1576
_ (length (ff 9))
8052
_

aimisiyou

有点小错误，最后插入0时，集合里面每个元素只存在两种情况，里面含有1个“*”，或者全部是数字（即2个1之间有1个数，2个2之间有2个数，2个n之间有n个数。 ），对于全是数字的情况，0可以放在头或者尾。

dlpg070

aimisiyou 发表于 2020-2-29 19:22
_ (length (ff 1))
1
_ (length (ff 2))

做的漂亮,
我比较了 前4项,数据一致
但有2个地方要修改,否则数列不一致.
根据王守恩约定:
1 首位的0要添加占位
2 许多首位比末尾大的要剔除 (去重复)
------------------------------------
aimisiyou 6#   与 dlpg070 3# 比较

_ (ff 1)
("101")               [ 1]  1, 0, 1,   

_ (ff 2)
("20121"   不符合约定                     
"12102")             [ 1], 1, 2, 1, 0, 2,

_ (ff 3)
("2302131" 不符合约定
"231213"  缺失 0     [ 2]  0, 2, 3, 1, 2, 1, 3,
"312132"  不符合约定
"1312032")           [ 1]  1, 3, 1, 2, 0, 3, 2,
           
_ (ff 4)
("240231413"          [ 3]  2, 4, 0, 2, 3, 1, 4, 1, 3,
"420324131" 不符合约定
"41312432"  不符合约定
"141302432"          [ 2]  1, 4, 1, 3, 0, 2, 4, 3, 2,
"234203141" 不符合约定
"23421314"  缺失 0   [ 4]  0, 2, 3, 4, 2, 1, 3, 1, 4,
"131423024"          [ 1]  1, 3, 1, 4, 2, 3, 0, 2, 4,
"314132042")不符合约定

dlpg070

dlpg070 发表于 2020-2-29 21:07
做的漂亮,
我比较了 前4项,数据一致
但有2个地方要修改,否则数列不一致.

我的结果:
an: 1,1,2,4,11,38,156,788,4158,---
看看去重复后是否一致?
有人讨论,很高兴.