iT邦幫忙

0

【組合學】給定節點數量,以python窮舉所有可能的rooted tree

問題描述: 固定節點數n,窮舉所有可能的rooted tree
例子:
當n=4時,共有4種可能性:

4
├── 1
├── 1
└── 1

4
├── 1
└── 2
    └── 1
    
4
└── 3
    ├── 1
    └── 1
    
4
└── 3
    └── 2
        └── 1

當n=5時,共有9種可能性:

5
├── 1
├── 1
├── 1
└── 1

5
├── 1
├── 1
└── 2
    └── 1

5
├── 1
└── 3
    ├── 1
    └── 1

5
├── 1
└── 3
    └── 2
        └── 1

5
├── 2
│   └── 1
└── 2
    └── 1

5
└── 4
    ├── 1
    ├── 1
    └── 1

5
└── 4
    ├── 1
    └── 2
        └── 1

5
└── 4
    └── 3
        ├── 1
        └── 1

5
└── 4
    └── 3
        └── 2
            └── 1

樹上的節點數字表示含自己節點在內,底下共有幾個節點,
這邊假設每個節點的子樹節點數量一定是遞增排列

程式實作

這邊我選擇用來實作的python模組為anytree,
可以方便的使用tree的結構,建立節點,
並內建能視覺化的畫出樹的長相

anytree不是內建模組,需要用指令pip install anytree安裝

想法就是遞迴去建樹
先寫一個用來做partition的函數:

def partitionsUsedLargerThanM(n, m):
    """
    函數功能:
    將n partition,並只能用大於m的數字
    例: partitionsUsedLargerThanM(4, 1)為:
    [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
    """
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return
    # modify partitions of n-1 to form partitions of n
    for i in range(m,n+1):
        for p in partitionsUsedLargerThanM(n-i, i):
    	    yield [i] + p

對於節點樹為n的樹,窮舉n-1的所有partition,
對於每個partition去組合窮舉所有的樹形(做cartesian product)

def enumTree(n):
    if n==1:
        return [Node(1)]
    res = []
    for p in partitionsUsedLargerThanM(n-1,1):
        treeList=[[t for t in enumTree(num)] for num in p]
        for trees in product(*treeList):
            # 注意要複製節點,不可只寫u = Node(n, children= trees)
            # 否則可能有有多個節點底下接到相同的節點物件
            u = Node(n, children= [copy.copy(t) for t in trees])
            res.append(u)
    return res

這邊再對遞迴邏輯解說一下,
假設要窮舉節點數量為5的樹,
首先root本身掛數字5,再來子樹的節點加起來總共是4,
所以窮舉4的partition有五種 ([[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]])
而得到節點數量為5的樹有以下五種可能性:

https://ithelp.ithome.com.tw/upload/images/20200823/20117114iqVkxSuzay.png
(圖是自己用小畫家畫的,不美觀請見諒)

圖中的每個三角形「i」為enumTree(i)的所有可能

完整測試程式

from anytree import Node, RenderTree
import time
import copy
from itertools import product

def partitionsUsedLargerThanM(n, m):
    """
    函數功能:
    將n partition,並只能用大於m的數字
    例: partitionsUsedLargerThanM(4, 1)為:
    [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
    """
	# base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return
	# modify partitions of n-1 to form partitions of n
    for i in range(m,n+1):
        for p in partitionsUsedLargerThanM(n-i, i):
    	    yield [i] + p
        

def enumTree(n):
    if n==1:
        return [Node(1)]
    res = []
    for p in partitionsUsedLargerThanM(n-1,1):
        treeList=[[t for t in enumTree(num)] for num in p]
        for trees in product(*treeList):
            # 注意要複製節點,不可只寫u = Node(n, children= trees)
            # 否則可能有有多個節點底下接到相同的節點物件
            u = Node(n, children= [copy.copy(t) for t in trees])
            res.append(u)
    return res

if __name__ == '__main__':
    tStart = time.time()#計時開始  
    count = 0  
    for tree in enumTree(5):
        count+=1
        for pre, fill, node in RenderTree(tree):
            print("%s%s" % (pre, node.name))
        print()
    tEnd = time.time()#計時結束
    print(count)
    print("Total time= %f seconds" % (tEnd - tStart))

尚未有邦友留言

立即登入留言