問題描述: 固定節點數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的樹有以下五種可能性:

(圖是自己用小畫家畫的，不美觀請見諒)

圖中的每個三角形「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))