已知列表和字典，列表是需排序元素，字典指明了元素间的优先关系，譬如 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)))
s3′ Python s1’ s2’11 条回复 • 2021-09-02 16:34:53 +08:00
toaruScar 1
toaruScar 5 小时 38 分钟前
可以弄成一个 class，然后用 functools.total_ordering 自定义对比函数。
MoYi123 2
MoYi123 5 小时 34 分钟前
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])

能用， 但是应该有更好的办法
Trim21 3
Trim21 5 小时 33 分钟前 via Android ❤️ 1
key=lambda x: {s1: 1 , s3: 2, s3: 3}.get(x, 0)
lonelinsky 4
lonelinsky 4 小时 59 分钟前
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 表示相等，又不用做任何操作，所以它已经排好序了
lonelinsky 5
lonelinsky 4 小时 51 分钟前
typo
S1 在 S3 前面 <=> S3 在 S1 后面
superhxl 6
superhxl 4 小时 30 分钟前
@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 没看懂。
lonelinsky 7
lonelinsky 3 小时 29 分钟前
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，直接打印就好了。
lonelinsky 8
lonelinsky 3 小时 25 分钟前
> 字典中的值表示相继访问的顺序
我好像理解错了，所以字典中的值会是 1，2，3 这样？是的话对字典按 value 排序，然后对 key 做个 reduce 就好了？
BBrother 9
BBrother 3 小时 24 分钟前
没看到你的问题，你是不是需要拓扑排序？
princelai 10
princelai 55 分钟前 ❤️ 2
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))
ipwx 11
ipwx 41 分钟前
@superhxl python 默认的不是两两比较排序，而是快速排序，只比 N log N 次。

所以你期待的 S1 < S3 + S3 < S2 imply S1 < S2 不存在。

你这个需求可以建图然后用拓扑排序。