在Python 3中基于分隔符("|")的两侧对字符串列表进行排序

Question

我正在寻找排序说明依赖关系的字符串列表(通过PC算法确定的贝叶斯网络的结构)。

。

verbose_struct = ['A', 'C|A,E', 'E', 'B|C,D', 'D']

sorted_struct = ['A', 'E', 'D', 'C|A,E', 'B|C,D']

字符串的顺序取决于依赖项(分隔符"|"后面的字母，例如B依赖于C和D)之前是否已列出。如上所述，'E'应该放在'C|A之前，因为C依赖于E。没有依赖关系的字符串应该放在所有有依赖关系的字符串之前。在"C|A,E"one_answers"B|C,D"之前加"D"。

我该怎么做呢?

我已经设法排序字符串是否有依赖使用以下:

sorted_struct = sorted(verbose_struct, key=lambda x: len(x.split('|')))

我不确定如何根据它们的依赖关系进一步对变量进行排序，因为我对Python中的lambda函数相当不熟悉。

Answer 1

我只会"让跳跃";这里做一个class来容纳这些物体。通过这样做，您可以实现自己的__lt__方法，这是所有默认排序方法对对象进行排序所需要的全部。

注意:这个示例类只处理"label "所以当你添加依赖性时，你只是添加了其他事物的标签。一个更复杂的类会保存依赖项的Element值，而不是标签，然后你可以通过查找依赖项的依赖项来把事情联系在一起，这在这个简单的例子中是做不到的。为了做到这一点，您需要以某种逻辑顺序(或者做一些更复杂的事情)来定义事物，以便首先添加树中最早的依赖项。可能有很多关于节点弧设置的例子(这就是本文所描述的)。

这里的主要内容是您可以创建一个自定义函数来通过比较2elements来启用排序。你也可以"剥掉"。这个包含两项的比较函数，在运行中生成片段，并将该函数传递给sort()方法，它也可以在没有类的情况下工作。

代码:

# Bayesian Elements
class Element():
def __init__(self, data: str):
self.label = data
if '|' in data:
# dependency...break it up
self.base, dependencies = data.split('|')
# break up the dependencies
self.dependencies = set(dependencies.split(','))
else:  # it is a single base element
self.base = data
self.dependencies = None
def get_dependencies(self):
return self.dependencies
def get_base(self):
return self.base
def get_label(self):
return self.label
def __str__(self):
return f'base: {self.base}, dep: {self.dependencies}'
def __repr__(self):
return self.label
# in order to compare class elements, you must create a custom "less than" function
# it is the basis of sort
def __lt__(self, other: 'Element'):
# case 1:  both are singletons, just alphabetically sort them:
if self.dependencies is None and other.dependencies is None:
return self.label < other.label
# case 2:  self has no dependencies, but other does
elif self.dependencies is None and other.dependencies is not None:
return True
# case 3:  other has no dependencies, self does
elif other.dependencies is None and self.dependencies is not None:
return False
# case 4:  both have dependencies, check if self depends on other:
else:
if self.base in other.dependencies:
return True
elif other.base in self.dependencies:
return False
else:  # sort by the base element
return self.base < other.base
data = ['B', 'A', 'C|A,E', 'E', 'B|C,D', 'D']
# make "elements" from the strings
elements = [Element(t) for t in data]
elements.sort()
print(elements)
# example
print(elements[4].get_dependencies())

输出:

[A, B, D, E, C|A,E, B|C,D]
{'A', 'E'}

Answer 2

理想情况下，您应该创建一个依赖树，并从添加和删除叶子开始。然而，对于像你这样简单的例子，你可以做一个简单的队列，并开始在你的调用"sorted"数组

import queue
a = list(filter(lambda x: len(x) == 1, verbose_struct ))
b = {x.split('|')[0]: tuple(x.split('|')[1].split(',')) for x in  filter(lambda x: len(x) > 1, verbose_struct )}
nodes = a[:]
q = queue.deque(b.keys())
while q:
cur = q.pop()
if all(map(lambda x: x in nodes, b[cur])):
nodes.append(cur[0])
a.append(f"{cur}|"  + ",".join(b[cur]))
else:
q.appendleft(cur)

a将是排序后的输出