已知列表和字典，列表是需排序元素，字典指明了元素间的优先关系，譬如 S1 需在 S3 之前，而 S3 又在 S2 之前。
s = ['S1','S2','S3']
val = {('S1','S3'):1,('S3','S2'):1}
希望得到的结果是['S1','S3','S2']，请问有何好的实现方式？
自己想用 python 中的 sort 的 cmp 参数进行排序，结果竟然没排序，不知原因。
from functools import cmp_to_key
s.sort(key=cmp_to_key(lambda x,y: val.get((x,y),0)))
 |
1
toaruScar Sep 2, 2021
可以弄成一个 class，然后用 functools.total_ordering 自定义对比函数。
|
 |
2
MoYi123 Sep 2, 2021
s = ['S1', 'S2', 'S3']
val = {('S1', 'S3'): 1, ('S3', 'S2'): 1} class S(str): ____def __lt__(self, other): ________if (self, other) in val: ____________return val[(self, other)] == 1 ________return False s = [S(i) for i in s] s.sort() print([str(i) for i in s]) 能用， 但是应该有更好的办法 |
 |
3
Trim21 Sep 2, 2021 via Android  1
key=lambda x: {s1: 1 , s3: 2, s3: 3}.get(x, 0)
|
 |
4
lonelinsky Sep 2, 2021
s = ['S1','S2','S3']
val = {('S1','S3'):-1,('S3','S2'):-1} # 这里你一开始的定义有点问题，如果你希望 S1 排在 S3 前面，则它的值应该是负的 s.sort(key=cmp_to_key(lambda x,y: val.get((x,y), -val.get((y,x), 0)))) # 这里你可能需要同时处理 (y, x) 的情况，如果你的定义是对称的。即 S1 在 S3 前面 <=> S3 在 S2 后面 注意你现在的方式里面对于未出现 val 里面的对，都会当成不需要排序的对象。如果你是像解决 AOE 网络的拓扑排序问题，建议直接看相关算法。 ============================= 你一开始的排序完全没用是因为排序时候，假设按序比较 (S1, S2) 你的 val 里面没有，返回 0 表示相等，不用做任何操作 (S2, S3) 你的 val 里面还是没有，返回 0 表示相等，又不用做任何操作，所以它已经排好序了 |
|
5
lonelinsky Sep 2, 2021
typo
S1 在 S3 前面 <=> S3 在 S1 后面 |
 |
6
superhxl OP @lonelinsky 我的定义没问题，也许有更好的方式。本身问题背景是若干个点，一次对这些点遍历，想要打印遍历的顺序。字典中的值表示相继访问的顺序，访问 S1 后访问 S3，访问 S3 后访问 S2.
关于 cmp 的应用再查查文档，这个确实是临时搜索的解决方案。 目前可以通过冒泡排序解决，但我想应该有更好办法。 ```python for p in range(len(s)-1): for q in range(p + 1, len(s)): if sol[z[(s[q],s[p])]] == 1: s[p], s[q] = s[q], s[p] ``` @toaruScar 去学习一下具体用法。 @MoYi123 好复杂的样子。 @Trim21 没看懂。 |
|
7
lonelinsky Sep 2, 2021
https://docs.python.org/3/library/functools.html#functools.cmp_to_key
A comparison function is any callable that accept two arguments, compares them, and returns a negative number for less-than, zero for equality, or a positive number for greater-than. 你定义的 1 会被认为是 greater-than，而默认排序是从小到大，所以你的定义和你的预期是反的，这是我说你定义有问题的地方，如果执意用 1 做定义的话，可以在 function 里面取个反就行。 你现在的定义里面不能保证任意两个元素的 cmp 结果都包含，比如你开始的定义里面 S1 和 S2 的大小关系没有显式定义，在冒泡这种会完全比较的排序方法中可能没问题，但是对于类似快排这种，排序中间可能会出现错误的结果。(这个地方是直觉，没有严格证明） > 本身问题背景是若干个点，一次对这些点遍历，想要打印遍历的顺序。 如果是这个问题的话，建议用 OrderedDict https://docs.python.org/3/library/collections.html#collections.OrderedDict，直接打印就好了。 |
|
8
lonelinsky Sep 2, 2021
> 字典中的值表示相继访问的顺序
我好像理解错了，所以字典中的值会是 1，2，3 这样？是的话对字典按 value 排序，然后对 key 做个 reduce 就好了？ |
 |
9
BBrother Sep 2, 2021
没看到你的问题，你是不是需要拓扑排序？
|
 |
10
princelai Sep 2, 2021 4
from networkx import DiGraph, draw_networkx, topological_sort
s = ['S1', 'S2', 'S3', 'S4', 'S5'] val = {('S1', 'S3'): 1, ('S3', 'S2'): 1, ('S5', 'S1'): 1, ('S2', 'S4'): 1} g = DiGraph() g.add_edges_from(val.keys()) s = list(topological_sort(g)) |
 |
11
ipwx Sep 2, 2021
@superhxl python 默认的不是两两比较排序，而是快速排序，只比 N log N 次。
所以你期待的 S1 < S3 + S3 < S2 imply S1 < S2 不存在。 你这个需求可以建图然后用拓扑排序。 |
 |
12
Pythoner666666 Sep 2, 2021
老谢 是你吗？？
|
 |
13
O5oz6z3 Sep 2, 2021
想到一个麻烦的做法：
def cmp(a, b): lt = val.get((a,b)) if lt == 1: return -1 gt = val.get((b,a)) if gt == 1: return 1 return -1 if a<b else 1 if a>b else 0 感觉像 #10 楼那样将 val 换成 set(val.keys()) 也没有问题。这个自定义排序似乎可以再加些功能，比如优先度排序？ |
|
16
superhxl OP @lonelinsky 明白了，多谢！对 collections 模块缺失不熟悉！
@princelai networkx 听说过，但没用过。果然学无止境。本来自己把顺序提取出来，就是为了绘图，采用 networkx 直接帮我把问题全解决了。 @Pythoner666666 ☻，认错人了！ 感谢楼上所有帮忙出注意的 V 友！ |
Select Language