In [ ]:
from IPython.display import display
from graphviz import Digraph
1. 生成子集¶
In [ ]:
def subsets(S):
if not S:
return [[]]
else:
x, sub = S[0], subsets(S[1:])
return sub + [([x]+s) for s in sub]
In [ ]:
subsets(['a'])
Out[ ]:
[[], ['a']]
In [ ]:
subsets(['red', 'green', 'blue'])
Out[ ]:
[[], ['blue'], ['green'], ['green', 'blue'], ['red'], ['red', 'blue'], ['red', 'green'], ['red', 'green', 'blue']]
In [ ]:
subsets('1234')
Out[ ]:
[[], ['4'], ['3'], ['3', '4'], ['2'], ['2', '4'], ['2', '3'], ['2', '3', '4'], ['1'], ['1', '4'], ['1', '3'], ['1', '3', '4'], ['1', '2'], ['1', '2', '4'], ['1', '2', '3'], ['1', '2', '3', '4']]
2. 生成排列¶
In [ ]:
def permutations(S):
if not S:
return [[]]
else:
res, perms = [], permutations(S[1:])
for i, _ in enumerate(S):
for perm in perms:
res.append(perm[:i] + [S[0]] + perm[i:])
return res
In [ ]:
permutations('abc')
Out[ ]:
[['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['c', 'a', 'b'], ['b', 'c', 'a'], ['c', 'b', 'a']]
In [ ]:
permutations([1, 2, 3, 4])
Out[ ]:
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 2, 3], [1, 3, 4, 2], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [3, 1, 2, 4], [4, 1, 2, 3], [3, 1, 4, 2], [4, 1, 3, 2], [2, 3, 1, 4], [2, 4, 1, 3], [3, 2, 1, 4], [4, 2, 1, 3], [3, 4, 1, 2], [4, 3, 1, 2], [2, 3, 4, 1], [2, 4, 3, 1], [3, 2, 4, 1], [4, 2, 3, 1], [3, 4, 2, 1], [4, 3, 2, 1]]
3. 绘制表达式树¶
In [ ]:
class Node:
def __init__(self, name, children=[]):
self.name = name
self.children = children
def render(self, G):
u = str(hash(self))
G.node(u, label=str(self.name), shape='circle')
for child in self.children:
child.render(G)
v = str(hash(child))
G.edge(u, v)
def render(lines):
for line in lines.strip().splitlines():
G = Digraph()
eval(line).render(G)
display(G)
# C++ 代码的输出
render(
'''
Node(name='+',children=[Node(name=1),Node(name=2)])
Node(name='+',children=[Node(name='()',children=[Node(name='+',children=[Node(name=1),Node(name=2)])]),Node(name='()',children=[Node(name='+',children=[Node(name=3),Node(name='+',children=[Node(name=4),Node(name=5)])])])])
Node(name='+',children=[Node(name=4),Node(name='+',children=[Node(name='()',children=[Node(name='+',children=[Node(name='+',children=[Node(name=1),Node(name=2)]),Node(name=3)])]),Node(name='()',children=[Node(name='+',children=[Node(name=3),Node(name='+',children=[Node(name=4),Node(name=5)])])])])])
Node(name='+',children=[Node(name='+',children=[Node(name='+',children=[Node(name='+',children=[Node(name=1),Node(name=1)]),Node(name='+',children=[Node(name='+',children=[Node(name=3),Node(name=4)]),Node(name=5)])]),Node(name=1)]),Node(name=1)])
'''
)
