O-tree表示法

aimisiyou · 发表于 2020-10-8 23:11:11

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

定个小目标，根据O-tree表示法自动画出排版图形。

aimisiyou · 发表于 2020-10-8 23:17:57

首先随机生成一个合法的O-tree编码，关键是T的编码。

aimisiyou · 发表于 2020-10-8 23:53:11

本帖最后由 aimisiyou 于 2020-10-8 23:56 编辑

_$  (defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(setq lst '(-1) n 20 i 1 flag t)
(while (and flag (< i n))
  (setq sum (apply '+ lst))
  (if (= sum 0)
   (setq lst (cons -1 lst))
   (if (= sum (- i n))
      (progn
      (setq flag nil)
   (repeat (- n i)
      (setq lst (cons 1 lst))
   )
   )
   (if (> (rnd) 0.5)
         (setq lst (cons -1 lst))
         (setq lst (cons 1 lst))
   )
)
)
(setq i (+ i 1))
)
(mapcar '(lambda (x) (/ (1+ x) 2)) (reverse lst))
RND
T
19
(0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 0 1 1)
_$

aimisiyou · 发表于 2020-10-9 00:04:55

本帖最后由 aimisiyou 于 2020-10-9 00:06 编辑

再生成n的一个排列
_$ (setq vlst nil)
(repeat 10
(setq vlst (cons (rnd) vlst))
)
(mapcar '1+ (vl-sort-i vlst '<))
nil
(0.86 0.7995 0.7159 0.6291 0.4273 0.4855 0.795 0.7166 0.5963 0.0385)
(10 5 6 9 4 3 8 7 2 1)
_$

aimisiyou · 发表于 2020-10-9 00:22:43

本帖最后由 aimisiyou 于 2021-2-22 21:50 编辑

_$ (defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (NN)
  (fix (* NN (rnd)))
)
(setq lst '(-1) n 10 i 1 flag t)
(while (and flag (< i n))
  (setq sum (apply '+ lst))
  (if (= sum 0)
   (setq lst (cons -1 lst))
      (if (= sum (- i n))
            (progn
                  (setq flag nil)
                        (repeat (- n i)
                           (setq lst (cons 1 lst))
                        )
               )
               (if (= (rem (rnd_n 1000) 2) 1)
                     (setq lst (cons -1 lst))
                     (setq lst (cons 1 lst))
               )
            )
      )
      (setq i (+ i 1))
)
(mapcar '(lambda (x) (/ (1+ x) 2)) (reverse lst))
RND
RND_N
T
8
(0 1 0 0 1 0 0 1 1 1)
_$

aimisiyou · 发表于 2020-10-9 00:24:20

_$ (setq vlst nil)
(repeat 10
(setq vlst (cons (rnd_n 1000) vlst))
)
(mapcar '(lambda (y) (if (= (rem (rnd_n 1000) 2) 1) y (* -1 y))) (mapcar '1+ (vl-sort-i vlst '<)))
nil
(454 106 736 396 831 951 599 219 715 151)
(-2 -10 -8 -4 -1 7 -9 -3 5 6)
_$

ynhh · 发表于 2020-10-9 20:17:06

加油
相信你

aimisiyou · 发表于 2020-10-10 00:27:30

本帖最后由 aimisiyou 于 2020-10-10 00:32 编辑

(setq vlst '(
(1 5.3 5.1)
(2 7.4 6.5)
(3 3.3 10.3)
(4 8.5 4.6)
(5 9.2 6.2)
(6 7.4 6.9)
(7 4.4 11.4)
(8 14.4 3.6)
(9 9.2 5.6)
))
(setq pt '(0 0))
(foreach en vlst
(command "rectang" pt "d" (cadr en) (caddr en) (polar pt 0 (caddr en)))
(setq pt (polar pt (/ pi 2) (caddr en)))
)

aimisiyou · 发表于 2020-10-10 00:34:49

本帖最后由 aimisiyou 于 2020-10-10 01:14 编辑

_$ (defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (NN)
  (fix (* NN (rnd)))
)
(setq lst '(-1) n 18 i 1 flag t)
(while (and flag (< i n))
  (setq sum (apply '+ lst))
  (if (= sum 0)
   (setq lst (cons -1 lst))
      (if (= sum (- i n))
            (progn
                  (setq flag nil)
                        (repeat (- n i)
                           (setq lst (cons 1 lst))
                        )
               )
               (if (= (rem (rnd_n 1000) 2) 1)
                     (setq lst (cons -1 lst))
                     (setq lst (cons 1 lst))
               )
            )
      )
      (setq i (+ i 1))
)
(mapcar '(lambda (x) (/ (1+ x) 2)) (reverse lst))
RND
RND_N
T
17
(0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1)
_$ (setq vlst nil)
(repeat 9
(setq vlst (cons (rnd_n 1000) vlst))
)
(mapcar '(lambda (y) (if (= (rem (rnd_n 1000) 2) 1)  y (* -1 y))) (mapcar '1+ (vl-sort-i vlst '<)))
nil
(21 480 905 457 118 755 378 879 694)
(-1 5 -7 4 -2 9 -6 8 -3)
_$
故根据O-tree表示法得到的布局图应为右图

aimisiyou · 发表于 2020-10-10 01:10:41

在随机运行得到一个O-tree表示，（T，Q）=((0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1)(5 2 -8 7 1 -4 -6 -3 9))
对应布局图为

aimisiyou · 发表于 2020-10-10 01:25:01

对于（（0 1 0 0 1 1）（-1 5 - 4））对应的应是右图。

aimisiyou · 发表于 2020-10-10 13:23:52

本帖最后由 aimisiyou 于 2020-10-11 10:17 编辑

紧凑排列规则有些类俄罗斯方块定位和下落规则，给定X值（即矩形左端位置），从最上方往下落，首先保证与左边相邻，同时不与下方的矩形块重叠。

aimisiyou · 发表于 2020-10-11 10:35:54

排完每一层后需要记录此时整体顶部状态（便于判断下一个矩形排放位置）。

aimisiyou · 发表于 2020-10-11 15:23:21

本帖最后由 aimisiyou 于 2020-10-11 16:11 编辑

可以将O-tree表示法中的0看成从左向右传递坐标并放置矩形，1看成从右向左传递坐标但不放置矩形。用一个表记录初始整体顶部轮廓，可以看成起点X=0，长度=n*max (Li),高度=0，即lst=(0,L，0)
放置矩形块1后，更新lst,lst=((0,d1_x,d1_y)(d1_x,L-d1_x,0))

aimisiyou · 发表于 2020-10-11 16:52:21

还需一个变量记录起始点角点坐标pt令pt=(0,0)，lst=(0,L,0),
放入矩形块1后，分别更新lst和pt,即
lst=((0,d1_x,d1_y)(d1_x,L-d1_x,0))
pt=(d1_x,0)
然后判断矩形块2的宽度与L-d1_x的大小，因为d2_x<L-d1_x,故矩形块可以角点pt放置，更新lst和pt
lst=((0,d1_x,d1_y)(d1_x,d2_x,d2_y)(d1_x+d2_x,L-d1_x-d2_x,0))
pt=(d1_x+d2_x,0)
按图O-tree表示法可知（（0 0 1 1 0……）（1 2 3……））
遇到1，pt往左退回前一个矩形块的水平距离，连续2个1后，pt退回到（0,0）
此时考虑放置矩形块3，因为d1_x<d3_x<d1_x+d2_x,故pt的纵坐标更新为块1、块2中y值的较大值，即pt=(0,d2_y)
再放置矩形块3，更新lst ,pt……

账号		自动登录	找回密码
密码			立即注册

[研讨] O-tree表示法

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分