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

Question

假设你取字符串'a'和'z'并按字母顺序列出它们之间的所有字符串:['a','b','c'...'x','y','z "].从这个列表的中点开始,你会发现'm'.所以这有点像取两个字符串的平均值.

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

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

我开始制作我自己的例程,简单地通过两个字符串并找到第一个不同字母的中点,这似乎在'aa'和'az'中点是'am'时工作得很好,但是然后它在'cat'上失败了,它认为是'c'的'小狗'中点.我尝试使用谷歌搜索"二进制搜索字符串中点"等但不知道我在这里尝试做什么的名称我没有运气.

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

Answer 1

如果您定义字符字母,您只需转换为基数10,执行平均值,然后转换回base-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

Answer 2

它听起来像你想要的,是将字母字符视为0和1之间的基数为26的值.如果你有不同长度的字符串(基数为10的例子),比如305和4202,那么你的中间点是3,因为你一次只看一个角色.相反,将它们视为浮点尾数:0.305和0.4202.从中可以很容易地得出.3626的中点(如果你愿意的话你可以圆).

对基数26(a = 0 ... z = 25,ba = 26,bb = 27等)做同样的事情来计算字母:

猫成为'a.cat'而小狗成为'a.doggie',做数学给猫的小数值为0.078004096,小狗的值为0.136390697,平均值为0.107197397,其中26基本上是"cumcqo"

Answer 3

如果您的意思是按字母顺序排列,只需使用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