已知列表和字典,列表是需排序元素,字典指明了元素间的优先关系,譬如 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 2021-09-02 11:37:44 +08:00
可以弄成一个 class,然后用 functools.total_ordering 自定义对比函数。
|
2
MoYi123 2021-09-02 11:40:58 +08:00
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 2021-09-02 11:42:03 +08:00 via Android 1
key=lambda x: {s1: 1 , s3: 2, s3: 3}.get(x, 0)
|
4
lonelinsky 2021-09-02 12:16:20 +08:00
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 2021-09-02 12:24:42 +08:00
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 2021-09-02 13:46:54 +08:00
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 2021-09-02 13:50:48 +08:00
> 字典中的值表示相继访问的顺序
我好像理解错了,所以字典中的值会是 1,2,3 这样?是的话对字典按 value 排序,然后对 key 做个 reduce 就好了? |
9
BBrother 2021-09-02 13:51:24 +08:00
没看到你的问题,你是不是需要拓扑排序?
|
10
princelai 2021-09-02 16:20:22 +08:00 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 2021-09-02 16:34:53 +08:00
@superhxl python 默认的不是两两比较排序,而是快速排序,只比 N log N 次。
所以你期待的 S1 < S3 + S3 < S2 imply S1 < S2 不存在。 你这个需求可以建图然后用拓扑排序。 |
12
Pythoner666666 2021-09-02 17:46:21 +08:00
老谢 是你吗??
|
13
O5oz6z3 2021-09-02 18:14:48 +08:00
想到一个麻烦的做法:
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 友! |