按字母/字典顺序排列的两个字符串的平均值

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

您可以将其扩展到具有多个字符的字符串，例如 'aa' 和 'zz' 之间的中点将位于列表的中间 ['aa', 'ab', 'ac' ... 'zx '、'zy'、'zz']。

可能有一个 Python 方法可以做到这一点吗？如果没有，即使知道算法的名称也会有所帮助。

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

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

如果定义字符字母表，则只需转换为基数 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

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

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