这个比较器功能可以用等效的键功能代替吗？

Question

假设我有一个比较器，它使用比较的两个值来决定排序。

例如，在这个问题中，我们必须使用一个使用两个元素的比较器函数：

def comparator(a, b): 
    ab = str(a) + str(b) 
    ba = str(b) + str(a) 
    return ((int(ba) > int(ab)) - (int(ba) < int(ab))) 

这个key=lambda x: ...在排序的时候可以写成格式吗？

我知道cmp_to_key存在将cmp函数转换为key函数的函数。我的问题是我们是否可以将其编写为键函数而不必以这种方式进行转换。

Answer 1

由于您已经排除了类似的解决方案functools.cmp_to_key（即使用 dunder 比较方法声明一个类），因此我推断您需要一种方法来执行此操作，其中关键函数仅使用内置类型。

问题在于，从逻辑上讲，像 25 这样的数字的关键是无限序列(2, 5, 2, 5, ...)。您需要无限序列的原因是您总是可能遇到像 252525252525253 这样的数字，其中比较的结果取决于最后一位数字，因为其余数字是另一个数字的重复序列。

如果你对输入数字的大小有限制（假设我们知道它们最多都是 10 位数字），那么序列只需要重复最多 10 位数字的长度，然后进行字典序比较（例如字符串或元组） ） 将工作：

def key_func(n, digits=10):
    s = str(n)
    return (s * digits)[:digits]

然而，正如 Stefan Pochmann 指出的那样，有一种内置类型Fraction可用于表示无限重复的数字序列：例如，(2, 5, 2, 5, ...)表示为，Fraction(25, 99)因为它的十进制扩展为0.2525...。比较分数相当于按字典顺序比较它们的小数展开式：

from fractions import Fraction

def key_func(n):
    k = len(str(n))
    return Fraction(n, 10**k - 1)

示例（两个关键功能相同）：

>>> sorted([54, 546, 548, 60], key=key_func)
[54, 546, 548, 60]
>>> sorted([1, 34, 3, 98, 9, 76, 45, 4], key=key_func)
[1, 3, 34, 4, 45, 76, 98, 9]
>>> sorted([25, 252525251], key=key_func)
[252525251, 25]
>>> sorted([25, 252525253], key=key_func)
[25, 252525253]

结果列表应该以相反的顺序连接，以通过串联产生最大可能的数字，因此例如[54, 546, 548, 60]映射到6054854654。