一个好玩的游戏

aimisiyou

先找出满足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")
_

aimisiyou

_ (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
_

aimisiyou

n=10时数据溢出了。表存储数据容易，但读取第i位置的数据用(nth  i   lst)，可能i数值会溢出。按字符串存贮可能计算的n要大一些。

aimisiyou

程序还可以优化，用nth函数的话，位置数受最大溢出数值限制。匹配查找过程可以简优化，采用布尔运算。

王守恩

王守恩 发表于 2020-2-25 17:58
补充几句。
1、此题三十年前很流行，几乎每个小朋友都在做。遗憾的是，不是每对数都有答案，
本人在此基 ...

同事们搓麻将、打扑克，小朋友也是挺烦人的。我说我来出道题，
用 0,1,1，0,1,1,2,2 把题意解释清楚，就让小朋友自己动手去折腾，
只要找到 1 个答案就可以！做对了再发 2 张牌，骗小朋友蛮好的。
也许来个小朋友第二天还在兴奋的告诉我：我把 9 做出来了！！
对于每个数都有解，我好像不怀疑，但不曾想某个数有多少解，
更不曾想有怎么多解！谢谢各位网友！

dlpg070

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

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

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

由于之前算法有瑕疵，导致结果有误。经修改，不考虑首尾限制的情况，得到的结果如下：
_ (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
_


没找到有关这个数列的信息。

aimisiyou

如果不包含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
_

这个数列到是找到了。