Python – 迭代自交叉引用

我有一个合理的挑战。 我有一个Excel表中包含标识符列和交叉引用列的单个表。 对于指示多个交叉引用的单个标识符可以有多行。 （请参阅下面的基本示例）

以字母“X”结尾的任何logging都表示它是交叉引用，而不是实际的标识符。 我需要为每个标识符生成交叉引用的列表，但是将其追踪到实际的交叉引用标识符。 所以用上面的“A1”作为例子，我需要返回如下列表“A2，A3，B1，B3”。 注意，列表中没有以“X”结尾的标识符，它们已经通过表格追溯到实际的源logging。

任何想法或帮助将不胜感激。 我正在使用python和xlrd来读取表。

Answer 1

t = [ ["a1","a2"], ["a1","a3"], ["a1","ax"], ["ax","b1"], ["ax","bx"], ["bx","b3"] ] import itertools def find_matches(t,key): return list(itertools.chain(*[[v] if not v.endswith("x") else find_matches(t,v) for k,v in t if k == key])) print find_matches(t,"a1") 

您可以将您的列表视为图的邻接matrix

就像是

 t = [ ["a1","a2"], ["a1","a3"], ["a1","ax"], ["ax","b1"], ["ax","bx"], ["bx","b3"] ] class MyGraph: def __init__(self,adjacency_table): self.table = adjacency_table self.graph = {} for from_node,to_node in adjacency_table: if from_node in self.graph: self.graph[from_node].append(to_node) else: self.graph[from_node] = [to_node] print self.graph def find_leaves(self,v): seen = set(v) def search(v): for vertex in self.graph[v]: if vertex in seen: continue seen.add(vertex) if vertex in self.graph: for p in search(vertex): yield p else: yield vertex for p in search(v): yield p print list(MyGraph(t).find_leaves("a1"))#,"a1")