两个字符串的字母顺序平均值

Question

假设你有两个字母，'a'和'z'，然后把它们之间的所有字母按字母顺序列出来：['a','b','c' ... 'x','y','z']。如果你找出这个列表的中间位置，你会得到'm'。这就像是在这两个字母之间找一个平均值。

你也可以把这个方法扩展到多个字母的字符串，比如说在'aa'和'zz'之间的中间位置，可以在这个列表的中间找到：['aa', 'ab', 'ac' ... 'zx', 'zy', 'zz']。

有没有可能在Python里有某个方法可以做到这一点呢？如果没有，知道这个算法的名字也会有帮助。

我开始自己写一个程序，简单地检查两个字符串，找出第一个不同字母的中间位置，这个方法在'aa'和'az'之间的中间是'am'，效果很好。但当我尝试'cat'和'doggie'时，它认为中间是'c'，这就不对了。我试着在网上搜索“二分查找字符串中点”等等，但因为不知道我在做什么，所以没找到合适的结果。

我把自己的解决方案添加到了回答中

Answer 1

如果你是说按字母顺序排列的话，可以直接使用FogleBird的算法，不过要把参数和结果反过来！

>>> print average('cat'[::-1], 'doggie'[::-1])[::-1]
cumdec

或者可以像这样重新写平均值

>>> def average(a, b):
...     a = debase(a[::-1])
...     b = debase(b[::-1])
...     return enbase((a + b) / 2)[::-1]
... 
>>> print average('cat', 'doggie')
cumdec
>>> print average('google', 'microsoft') 
jlvymlupj
>>> print average('microsoft', 'google') 
jlvymlupj

Answer 2

听起来你想做的是把字母当作一种从0到1的26进制值来处理。当你有不同长度的字符串（比如在10进制下的305和4202），你会发现它们的中间值是3，因为你是一个一个字符地看。其实可以把它们当作浮点数的小数部分来看：0.305和0.4202。这样算出来的中间值就很简单了，大约是0.3626（你可以选择四舍五入）。

对字母也用同样的方法来处理26进制（a=0...z=25，ba=26，bb=27，等等），这样就能进行计算：

比如“cat”可以变成'a.cat'，而“doggie”变成'a.doggie'，通过计算，“cat”的十进制值是0.078004096，“doggie”的值是0.136390697，平均值大约是0.107197397，在26进制下大概是“cumcqo”。

Answer 3

如果你定义了一组字符作为字母表，你可以把这些字符转换成十进制数字，计算一个平均值，然后再把这个平均值转换回字母表的基数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