数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 完美间隔配对排列
123456下一页
返回列表 发新帖
楼主: 王守恩

[擂台] 完美间隔配对排列

[复制链接]
aimisiyou
发表于 2020-2-29 21:38:35 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-3-1 00:34 编辑

先找出满足2个1之间有1个数，2个2之间有2个数……2个n之间有n个数的所有情况，剩下的就是剔除工作了，这个不难。
(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 3))
              (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 (vl-remove nil (mapcar '(lambda (y) (if (= "0" (substr y 1 1))
                                                      (if (<= (substr y 2 1) (substr y num 1))
                                                                                                               y
                                                                                                                   nil
                                                                                                          )
                                                                                                          (if (<= (substr y 1 1) (substr y num 1))
                                                                                                              y
                                                                                                                  nil
                                                                                                           )
                                                                                                   )
                                                                                 )
                                   (apply 'append (mapcar '(lambda (x)
                             (if (vl-string-search "*" x)
                                  (list (vl-string-translate "*" "0" x))
                                                                  (list (strcat "0" x) (strcat x  "0"))
                                                          )
                                                        ) strlst))
                                                        )
                                                        )
        )   
)
FF
_ (ff 1)
("101")
_ (ff 2)
("12102")
_ (ff 3)
("0231213" "1312032")
_ (ff 4)
("240231413" "141302432" "023421314" "131423024")
_ (ff 5)
("14135243205" "20425314135" "14153042352" "23425314105" "13145320425" "20524131543" "15104235243" "30523421514" "31513420524" "15123425304" "15103425324")
_ (ff 6)
("2612145360435" "4260245316135" "4161345236205" "4263245316105" "3161345026425" "2612153460354" "3046325421615" "1016425324635" "1316435024625" "1613504362542" "3062352416154" "1612532463504" "2632503461514" "1416254230653" "2042635413165" "1416354032652" "2342635410165" "2462514136503" "1014635243265" "1314635240265" "2062514136543" "1016352432654" "2362531416504" "1413564320526" "1415604235263" "1014562342536" "2562141536403" "1015623425364" "1415364235206" "1015364235246" "1516304532642" "3450364251216" "1514603542362" "1512642530463" "1510642532463" "3151364250246" "1510463524326" "2532463514106")
_

评分

参与人数 1威望 +2 金币 +2 贡献 +2 经验 +2 鲜花 +2 收起 理由
王守恩 + 2 + 2 + 2 + 2 + 2 能把 (ff 7) 发出来吗？

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

aimisiyou
发表于 2020-2-29 21:46:18 | 显示全部楼层
_ (length (ff 1))
1
_ (length (ff 2))
1
_  (length (ff 3))
2
_ (length (ff 4))
4
_ (length (ff 5))
11
_ (length (ff 6))
38
_ (length (ff 7))
156
_ (length (ff 8))
788
_ (length (ff 9))
4130
_

点评

dlpg070
我不怀疑你的算法,怀疑我的结果,希望借助你的数据查找我的错误原因  发表于 2020-3-1 09:14
aimisiyou
算法有瑕疵，根节点往下分支时，根节点字符前后添加"*"的个数应为max{k+2,2*n-strlen(根节点字符)}，匹配按k+2位从左到右  发表于 2020-3-1 09:00
aimisiyou
首先要确保算法的正确性，然后就是提高程序运行效率的事。  发表于 2020-3-1 08:47
aimisiyou
算法我在那张图里已经说明了，每个节点的字符长度不能大于(2n+1)，最终的结果不会有遗漏。你按那张图的算法对照下。  发表于 2020-3-1 08:34
dlpg070
除了n=9 ,我们两人结果一样,能否把n=9数据以附件形式贴出来?  发表于 2020-3-1 08:15
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

aimisiyou
发表于 2020-2-29 22:11:56 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-3-1 08:38 编辑

n=10时数据溢出了。表存储数据容易，但读取第i位置的数据用(nth  i   lst)，可能i数值会溢出。按字符串存贮可能计算的n要大一些。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

aimisiyou
发表于 2020-3-1 08:35:11 | 显示全部楼层
程序还可以优化，用nth函数的话，位置数受最大溢出数值限制。匹配查找过程可以简优化，采用布尔运算。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

dlpg070
发表于 2020-3-1 09:54:34 | 显示全部楼层
aimisiyou 发表于 2020-3-1 08:35
程序还可以优化，用nth函数的话，位置数受最大溢出数值限制。匹配查找过程可以简优化，采用布尔运算。

我的搜索法较笨,n大时很慢,结果直接存盘,得数列:
1, 1, 2, 4, 11, 38, 156,  788,  4158,  23384      
耗时 3246.78秒
n=9    4158,  
n=10 23384   
待验证,请帮助
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

aimisiyou
发表于 2020-3-1 10:23:19 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-3-1 10:29 编辑
dlpg070 发表于 2020-3-1 09:54
我的搜索法较笨,n大时很慢,结果直接存盘,得数列:
1, 1, 2, 4, 11, 38, 156,  788,  4158,  23384        ...


如果不考虑首尾大小比较（只要满足2个1之间有1个数，2个2之间有2个数……2个n之间n个数。0分别放在头和尾算2种结果），有兴趣仅仅算下n较大时所有结果的个数吗？当然要考虑避免数值溢出的情况。比如n=20的结果数。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

dlpg070
发表于 2020-3-1 10:34:08 | 显示全部楼层
本帖最后由 dlpg070 于 2020-3-1 12:52 编辑
aimisiyou 发表于 2020-3-1 10:23
如果不考虑首尾大小比较（只要满足2个1之间有1个数，2个2之间有2个数……2个n之间n那个数。0分别放在头 ...


非常希望n=20的结果,对于我这是不可能完成的任务,OEIS中有许多类似数列,期待你的杰作
最好还是去重复的(首位比较的目的是去重).OEIS中多数是去重的
例如:A00088 Number of graphs on n unlabeled nodes.
1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952,
29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776,
1787577725145611700547878190848, 24637809253125004524383007491432768
与此题多么相似,前5项完全一样,a(7)也相同,列出20项
注意这个很老的问题至今有人研究,最新的mma代码是2019年的:Jean - Fran?ois Alcover, Dec 03 2019, after Alois P.Heinz
乐见你的算法的神通
如果能求出数列前20项,或可收录到OEIS

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

aimisiyou
发表于 2020-3-1 17:54:57 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-3-1 18:04 编辑

由于之前算法有瑕疵，导致结果有误。经修改，不考虑首尾限制的情况，得到的结果如下：
_ (length (ff 1))
1
_ (length (ff 2))
2
_ (length (ff 3))
6
_ (length (ff 4))
10
_ (length (ff 5))
22
_ (length (ff 6))
76
_ (length (ff 7))
364
_ (length (ff 8))
1876
_ (length (ff 9))
8316
_


没找到有关这个数列的信息。
kkk.png
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

aimisiyou
发表于 2020-3-1 18:26:14 | 显示全部楼层
如果不包含0。则
_ (defun ff (n)
(setq num (+ n n 1))
(defun f (k)
  (setq str "")
  (repeat k
    (setq str (strcat "0" str))
   )
)
(defun fstr (kk sstr)
   (setq nkk (max (+ kk 2) (- num (strlen sstr))) vlst nil)
   (setq sstr (strcat (f nkk) sstr (f nkk)))
   (setq slst (mapcar '(lambda (x) (- x 48)) (vl-string->list sstr)))
   (setq nlst (mapcar '(lambda (x) (if (= x 0) 1 0)) slst))
   (setq nnlst (mapcar '(lambda (x) (- x 48)) (vl-string->list  (strcat "1" (f  kk) "1"))))
   (while (<= (length nnlst) (length nlst))
         (if (= 2 (apply '+ (mapcar '(lambda (x y) (boole 1 x y)) nnlst nlst)))
                     (progn  
                             (setq ntlst (mapcar '+ slst (mapcar '(lambda (y) (* y kk)) nnlst)))
                                 (setq str1 (vl-list->string (mapcar '(lambda (x) (+ 48 x)) ntlst)))
                 (setq str_new (vl-string-subst str1 (substr sstr 1 (strlen str1)) sstr))
                             (setq str_new (vl-string-right-trim "0" (vl-string-left-trim "0" str_new)))
                                 (if (<= (strlen str_new) num)
                     (setq vlst (cons str_new  vlst))
                                  )
                          )
                   )
             (setq nnlst (cons 0 nnlst))
           )
        vlst
)
(setq str_n (strcat (itoa n) (f n) (itoa n)) vvlst (list str_n))
(while (> n 1)
        (setq vvlst (apply 'append (mapcar '(lambda (x) (fstr (- n 1) x)) vvlst)))
        (setq n (- n 1))
)
  (setq vvlst  (vl-remove nil (mapcar '(lambda (x)
                             (if (vl-string-search "0" x)
                                 nil
                                                                 x)
                                                          )
                                                        vvlst)
                                )   
  )
)
FF
_ (ff 1)
nil
_ (ff 2)
nil
_ (ff 3)
("312132" "231213")
_ (ff 4)
("41312432" "23421314")
_ (ff 5)
nil
_ (ff 6)
nil
_ (ff 7)
("27423564371516" "72452634753161" "74151643752362" "71316435724625" "71416354732652" "17125623475364" "57141653472362" "73161345726425" "17126425374635" "72462354736151" "24723645317165" "57236253471614" "35723625417164" "57416154372632" "35743625427161" "52732653417164" "15173465324726" "72632453764151" "37463254276151" "41716425327635" "73625324765141" "23726351417654" "57263254376141" "34573641512762" "51716254237643" "52472654131763" "36713145627425" "34673245261715" "26721514637543" "14167345236275" "45671415362732" "14156742352637" "53672352461714" "15167245236473" "15146735423627" "62742356437151" "46171435623725" "16172452634753" "23627345161475" "46171452632753" "41617435263275" "56171354632742" "15163745326427" "53647352462171" "52462754316137" "26327435614175" "46357432652171" "25623745361417" "52642753461317" "26325734615147" "16135743625427" "61517346532472")
_ (length (ff 1))
0
_  (length (ff 2))
0
_ (length (ff 3))
2
_ (length (ff 4))
2
_ (length (ff 5))
0
_ (length (ff 6))
0
_ (length (ff 7))
52
_ (length (ff 8))
300
_ (length (ff 9))
0
_

这个数列到是找到了。
pk.png
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
 楼主| 发表于 2020-3-1 19:20:45 | 显示全部楼层
本帖最后由 王守恩 于 2020-3-1 19:52 编辑
aimisiyou 发表于 2020-3-1 18:26
如果不包含0。则
_ (defun ff (n)
(setq num (+ n n 1))

_ (ff 1=1)
1, "101"
_ (ff 2=1)
1, "12102"
_ (ff 3=2)
1, "0231213"
2, "1312032"
_ (ff 4=4)
1, "023421314"
2, "131423024"
3, "141302432"
4, "240231413"
_ (ff 5=11)
01, "13145320425"
02, "14135243205"
03, "14153042352"
04, "15103425324"
05, "15104235243"
06, "15123425304"
07, "20425314135"
08, "20524131543"
09, "23425314105"
10, "30523421514"
11, "31513420524"
_ (ff 6=38)
01, "1014562342536"
02, "1014635243265"
03, "1015364235246"
04, "1015623425364"
05, "1016352432654"
06, "1016425324635"
07, "1314635240265"
08, "1316435024625"
09, "1413564320526"
10, "1415364235206"
11, "1415604235263"
12, "1416254230653"
13, "1416354032652"
14, "1510463524326"
15, "1510642532463"
16, "1512642530463"
17, "1514603542362"
18, "1516304532642"
19, "1612532463504"
20, "1613504362542"
21, "2042635413165"
22, "2062514136543"
23, "2342635410165"
24, "2362531416504"
25, "2462514136503"
26, "2532463514106"
27, "2562141536403"
28, "2612145360435"
29, "2612153460354"
30, "2632503461514"
31, "3046325421615"
32, "3062352416154"
33, "3151364250246"
34, "3161345026425"
35, "3450364251216"
36, "4161345236205"
37, "4260245316135"
38, "4263245316105"
_ (ff 7=156)
..........
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

123456下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2025-4-19 07:30 , Processed in 0.167253 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表