python - 按字母/字典顺序计算两个字符串的平均值

Question

假设您使用字符串 'a' 和 'z' 并按字母顺序列出它们之间的所有字符串:['a','b','c' ... 'x','y' ,'z']。取此列表的中点，您会找到“m”。所以这有点像取这两个字符串的平均值。

您可以将其扩展到包含多个字符的字符串，例如，可以在列表 ['aa', 'ab', 'ac' .. . 'zx', 'zy', 'zz'].

某处是否有 Python 方法可以执行此操作？如果不知道，即使知道算法的名称也会有所帮助。

我开始制作我自己的例程，它简单地遍历两个字符串并找到第一个不同字母的中点，这在 'aa' 和 'az' 中点是 'am' 的情况下似乎很有效，但后来它在它认为是“c”的“cat”、“doggie”中点上失败。我尝试使用谷歌搜索“二进制搜索字符串中点”等，但不知道我在这里尝试做的事情的名称，我运气不佳。

我添加了自己的解决方案作为答案

Answer 1

如果您定义字符字母表，您只需转换为以 10 为底数，取平均值，然后转换回以 N 为底数，其中 N 是字母表的大小。

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def enbase(x):
    n = len(alphabet)
    if x < n:
        return alphabet[x]
    return enbase(x/n) + alphabet[x%n]

def debase(x):
    n = len(alphabet)
    result = 0
    for i, c in enumerate(reversed(x)):
        result += alphabet.index(c) * (n**i)
    return result

def average(a, b):
    a = debase(a)
    b = debase(b)
    return enbase((a + b) / 2)

print average('a', 'z') #m
print average('aa', 'zz') #mz
print average('cat', 'doggie') #budeel
print average('google', 'microsoft') #gebmbqkil
print average('microsoft', 'google') #gebmbqkil

编辑:根据评论和其他答案，您可能希望通过将字母表的第一个字母附加到较短的单词直到它们的长度相同来处理不同长度的字符串。这将导致“平均值”落在字典排序中的两个输入之间。下面的代码更改和新输出。

def pad(x, n):
    p = alphabet[0] * (n - len(x)) 
    return '%s%s' % (x, p)

def average(a, b):
    n = max(len(a), len(b))
    a = debase(pad(a, n))
    b = debase(pad(b, n))
    return enbase((a + b) / 2)

print average('a', 'z') #m
print average('aa', 'zz') #mz
print average('aa', 'az') #m (equivalent to ma)
print average('cat', 'doggie') #cumqec
print average('google', 'microsoft') #jlilzyhcw
print average('microsoft', 'google') #jlilzyhcw