Pyslvs v0.9 大更新進度

拓樸排列程式

拓樸排列程式

花了一些時間寫了一個排列拓樸程式，將概念寫在這邊。

在論壇爬文時，看到作者自己推薦的 Python 樹狀結構模組 anytree，看了說明文件後決定使用此模組協助樹狀管理。

以一個四連桿 (4,) 的樹狀拓樸如下，只有一種排列方法：

L0(2)
├── L1(2)
│   └── L3(2)
│       └── [L2](2)
└── L2(2)
    └── [L3](2)
-------
Answer count: 1

需要的模組有：

from anytree import Node, RenderTree
from anytree.search import findall
from itertools import permutations
from typing import Tuple

接著是印出上面樹狀結構的函式，anytree 的 RenderTree 搜尋函式會朝下列出節點的階級字元。

這邊用 noname 這個 bool 變數決定是否顯示名稱。

show_tree = lambda root: '\n'.join("{}{}({})".format(pre, n.name, n.limit) for pre, fill, n in RenderTree(root))

接下來是主函式，稱為 make_link，接收內含 int 的可迭代物件。

def topo(iter: Tuple[int,]):
    ...
    return answer

第一部分是創出連桿的數量，數字則是接頭數。

link_type = []
  for i, num in enumerate(iter):
    i += 2
    for j in range(num):
        link_type.append(i)

如輸入 (4,)，可以得到 [2, 2, 2, 2]；輸入 (5, 4) 可得 [2, 2, 2, 2, 2, 3, 3, 3, 3]。

使用 Python 迭代工具模組的 permutations 函式來創造排列組合的迴圈。

相符無誤的項目會將 root 節點加入答案，有錯誤則用 continue 關鍵字跳過。

answer = []
for all_link in list(set(permutations(link_type))):
  ...
  answer.append(links[0])

首先轉換 link_type 的內容成為 anytree 模組的 Node 類型。

其中 limit 屬性是此節點的接頭上限，僅用於比對，並無程式上的限制。

all_link = [Node("L{}".format(i), limit=v) for i, v in enumerate(all_link)]

接著將第一項當作 root 節點，加入 links。

這裡 links 清單的最後一項 links[-1] 是接下來的搜索法準備填入的項目。

links = []
links.append(all_link.pop(0))

然後使用廣度優先搜索法 (Breadth-First-Search, BFS) 填入所有節點，使用 list 類型的 pop 方法配上 while 迴圈可以確保用光所有節點。

當指派一個節點的 parent 屬性時，anytree 模組會自動將節點連上父節點，父節點可以透過 children 屬性取得一個裝有所有子節點指標的 tuple 物件。

while all_link:
    link = all_link.pop(0)
    if (len(links[-1].children) + bool(links[-1].parent))==links[-1].limit:
        links.append(links[-1].children[0])
    link.parent = links[-1]

由於數學定義的「樹 (tree)」結構中，子節點只能擁有一個父項，否則為迴路 (Loop)，anytree 模組會在連接成迴路時自動回擲 LoopError 錯誤。

但是我們的運動鍊為 close chain，因此必須再創立一個配對流程，這次使用類似連結的概念，同時為「主體」連結一個虛擬節點。

虛擬節點的樣式使用中括弧 [ ] 辨識，不用指派名稱。

創立 get_no_done 函式回傳使用 anytree 的 findall 模組過濾沒配對完成的節點。

get_no_done = lambda: findall(links[0], filter_=lambda n: '[' not in n.name and (len(n.children) + bool(links[-1].parent)) < n.limit)
error = False
while get_no_done():
    nodes = get_no_done()
    try:
        l_1, l_2 = nodes[0], nodes[1]
    except (ValueError, IndexError):
        error = True
        break
    else:
        Node("[{}]".format(l_1.name), limit=str(l_1.limit), parent=l_2)
        Node("[{}]".format(l_2.name), limit=str(l_2.limit), parent=l_1)

最後檢查是否在上述迴圈出現沒閉合狀況。

if error:
    continue

或是兩對連桿之間有連到一個以上的接頭。

if findall(links[0], filter_=lambda n: len(n.children)!=len(set(c.name.replace('[', '').replace(']', '') for c in n.children))):
    continue

最後可以進行測試：

if __name__=='__main__':
    print("Topologic test")
    answer = topo([5, 4])
    #Show tree
    for root in answer:
        print(show_tree(root))
        print('-'*7)
    print("Answer count: {}".format(len(answer)))

可得：

...
-------
L0(2)
├── L1(3)
│   ├── L3(2)
│   │   └── L5(2)
│   │       └── L6(3)
│   │           ├── L7(2)
│   │           │   └── [L8](3)
│   │           └── L8(3)
│   │               ├── [L7](2)
│   │               └── [L4](3)
│   └── L4(3)
│       ├── [L8](3)
│       └── [L2](2)
└── L2(2)
    └── [L4](3)
-------
Answer count: 36

經驗證，所有接頭都有連接。

Pyslvs 開發進度 - 12/05

拓樸排列程式

Comments