多个数组，每个数组中选择一项，总共能有多少种组合，treelib实现

问题来源：《有意思的面试题-数独问题》

《多个数组，每个数组中选择一项，总共能有多少种组合，reduce函数实现》

啥时候遇到这种问题

这种问题，我认为是路径问题，以下面的两个数组举例，第一次有2个选择，然后再选，还有2个选择。总共有2x2=4种选择。 [1, 2], [3, 4] 总共有2x2=4种选择。 [1, 2], [3, 4],[5, 6, 7, 8] 总共 2x2x4=8中选择。

大数据处理的时候肯定遇到

数据小还很方便的，但我遇到了，这些路径的组合：

[[6, 8], [2, 5], [1, 9], [3, 9], [3, 5], [3, 9], [8, 9], [3, 6], [2, 9], [2, 3, 8], [2, 3, 6], [2, 5, 8], [1, 5, 8], [1, 6, 9], [5, 6, 9], [1, 3, 5], [3, 5, 6], [3, 8, 9]]

这些字符串的组合总共有2x2x2x2x2x2x2x2x2x3x3x3x3x3x3x3x3x3，这么多种组合。 所以我就使用tree中数据结构。我现在的是python版本的treelib。

treelib for python入门教程

这个是摘自https://treelib.readthedocs.io/en/latest/官方文档的一串代码，用于感性认识吧。

>>> from treelib import Node, Tree >>> tree = Tree() >>> tree.create_node("Harry", "harry") # root node >>> tree.create_node("Jane", "jane", parent="harry") >>> tree.create_node("Bill", "bill", parent="harry") >>> tree.create_node("Diane", "diane", parent="jane") >>> tree.create_node("Mary", "mary", parent="diane") >>> tree.create_node("Mark", "mark", parent="jane") >>> tree.show() Harry ├── Bill └── Jane ├── Diane │ └── Mary └── Mark

简单API介绍：

1.创建树： tree = Tree()

2.以树型结构进行打印： tree = Tree()

3.获取所有从根节点到叶子节点的路径，返回的是一个list结构，里面存贮的是node的ID，ID为string类型。 tree.paths_to_leaves()

4.移除以一个节点，同时移除其所有的子节点 ,返回值为移除的节点个 tree.remove_node( identifier)

5.返回所有叶节点对象list列表，若给定root则返回以root为根节点的树的所有叶节点对象list列表 leaves(self, root=None)

实例代码：

import numpy as np from treelib import Node, Tree def getAllWay(data): tree = Tree() #创建了第一个节点，第一个节点没啥用处，之后要去掉。 tree.create_node(data=0) #开始插入数据，以这些数据举例，[6, 8], [2, 3, 5], [1, 9] # 0 # / \ # / \ # 6 8 # / | \ / | \ # / | \ / | \ # 2 3 5 2 3 5 # / \ / \ / \ / \ / \ / \ # 1 9 1 9 1 9 1 9 1 9 1 9 #最终组成的路径为 # [6,2,1]; [6,2,9]; [6,3,1]; [6,3,9]; [6,5,1]; [6,5,9]; # [8,2,1]; [8,2,9]; [8,3,1]; [8,3,9]; [8,5,1]; [8,5,9]; for line in data: leavesList = tree.leaves() for node in leavesList: for item in line: #这里是挨个插入，data部分就是记录的数据。 tree.create_node(tag=str(item), parent = node, data=item) return tree def main(): # data = [[6, 8], [2, 5], [1, 9], [3, 9], [3, 5], [3, 9], [8, 9], [3, 6], [2, 9], [2, 3, 8], # [2, 3, 6], [2, 5, 8], [1, 5, 8], [1, 6, 9], [5, 6, 9], [1, 3, 5], [3, 5, 6], [3, 8, 9]] data = [[6, 8], [2, 3, 5], [1, 9], [3, 9]] tree = getAllWay(data) print('get all way success ') #在这里就是获取所有到达叶子的路径 paths = tree.paths_to_leaves() #获得之后获得一个路径的table表格。 #[[路径1], # [路径2], # [路径3]] matH = [] for path in paths: matW = [] #去除了root节点的数据。 for id in path[1:]: node = tree.get_node(id).data matW.append(node) matH.append(matW) # print(type(node)) print(matH) if __name__ == "__main__": main();