排数字游戏

mahuan1279

用0,1,1,2,2,3,3,3,4,4……n,n排位，使得2个1之间有1个数，2个2之间有2个数，2个3之间有3个数……2个n之间有n个数。求满足要求的所有排位。

mahuan1279

其实就是多叉树裁枝查找过程，符合条件的继续往下分枝。可以编程序找到所有解。核心问题是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替换插入，得到所有的结果。

mahuan1279

_$ (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  (apply 'append (mapcar '(lambda (x)
                             (if (vl-string-search "0" x)
                                 (list x)
                                                                 (list (strcat "0" x) (strcat x "0"))
                                                          )
                                                        )
                                                        vvlst)
                                )   
  )
)
FF
_$ (ff 1)
("101")
_$ (ff 2)
("20121" "12102")
_$ (ff 3)
("0312132" "3121320" "1312032" "2302131" "0231213" "2312130")
_$ (ff 4)
("420324131" "240231413" "041312432" "413124320" "141302432" "234203141" "023421314" "234213140" "314132042" "131423024")
_$ (ff 5)
("15103425324" "50234253141" "15123425304" "50141352432" "15104235243" "53141352402" "25324035141" "31513420524" "30523421514" "52402354131" "20524131543" "34513142502" "13145320425" "41512432503" "42502431513" "14153042352" "20425314135" "34253240151" "23425314105" "40352432151" "14135243205" "42352430151")
_$ (ff 6)
("2612145360435" "6014153642352" "6234253640151" "6121524630543" "2612153460354" "2632453064151" "3161345026425" "6420524631513" "3640352462151" "3642352460151" "4260245316135" "4161345236205" "4263245316105" "6025324635141" "1612532463504" "2632503461514" "1613504362542" "3062352416154" "6425324635101" "1016425324635" "1316435024625" "2462354036151" "3046325421615" "6250234653141" "3625324065141" "2362531416504" "2062514136543" "6352432654101" "1016352432654" "2462514136503" "4635243265101" "1014635243265" "3046351412652" "1314635240265" "1416254230653" "1416354032652" "2042635413165" "2342635410165" "5610145362432" "5613145362402" "2562304536141" "3560324526141" "5620425364131" "2562141536403" "5623425364101" "1015623425364" "3056314152642" "4562342536101" "1014562342536" "3456314152602" "4056141352632" "1415604235263" "1413564320526" "5161245236403" "1516304532642" "5264205346131" "5364235246101" "1015364235246" "4516142532603" "2452634053161" "4151643052362" "4053642352161" "1415364235206" "5016135423624" "5026325431614" "5316135420624" "1510642532463" "1512642530463" "3151364250246" "5246205431613" "1514603542362" "4530643512162" "3450364251216" "1510463524326" "2532463514106" "5340635412162")
_$

mahuan1279

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

mahuan1279

;;;程序跑了6小时得出(length (ff 11))=320208
;;;求f(10) 按30分钟计算，求f(11)所花时间理论上为30分钟*22*23=4.2小时，与实际6小时左右偏差不多。
;;;按此粗略估计求(length (ff 12))所花时间为6小时*24*25=150天=5个月！！！
_$ (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 (vl-list->string (list (+ 48 n))) (f n) (vl-list->string (list (+ 48 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  (apply 'append (mapcar '(lambda (x)
                             (if (vl-string-search "0" x)
                                 (list x)
                                                                 (list (strcat "0" x) (strcat x "0"))
                                                          )
                                                        )
                                                        vvlst)
                                )   
  )
)
FF
_$ (ff 1)
("101")
_$ (ff 2)
("20121" "12102")
_$ (ff 3)
("0312132" "3121320" "1312032" "2302131" "0231213" "2312130")
_$ (length (ff 9))
8316
_$ (length (ff 10))
46768
_$ (length (ff 11))
320208