logo标签列表

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

pythonalgorithm
8
假设您拿到了字符串'a'和'z'，并将它们之间的所有字符串按字母顺序列出：['a'，'b'，'c' ... 'x'，'y'，'z']。找到这个列表的中点，你会发现'm'。所以这有点像取这两个字符串的平均值。
您可以将其扩展到具有多个字符的字符串，例如在列表['aa'，'ab'，'ac' ... 'zx'，'zy'，'zz']的中间找到'aa'和'zz'的中点。
可能有一个Python方法可以做到这一点吗？如果没有，知道算法的名称甚至也有帮助。
我开始编写自己的例程，简单地遍历两个字符串，并找到第一个不同字母的中点，这似乎在'aa'和'az'的中点为'am'时运行良好，但是在'cat'，'doggie'的中点失败，因为它认为中点是'c'。我尝试通过谷歌搜索“二分查找字符串中点”等，但是由于不知道我正在尝试做什么的名称，所以没有什么收获。
我添加了自己的解决方案作为答案。
1
当字符串长度不同时，你该怎么办？ - Pillsy
可用的字母表只有小写字母a-z吗？ - FogleBird
好问题。更重要的是，我正在尝试将大型单词列表分成大致两个不同的部分，而无法事先知道单词列表的大小。我只知道第一个和最后一个字符串，并且必须根据中点来做一个有教养的猜测，以进行一种二分搜索（它们是在bigtable中的Google应用引擎键）。 - Bemmu
它们可以是任何ASCII字符串。 - Bemmu
这是bigtable中的两个键，需要大约20小时才能找到length(x)的长度。 - Bemmu
8个回答
9

如果您定义了一个字符表，您可以将其转换为十进制，进行平均值计算，然后再转换回基数为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
2
但是，“budeel”似乎不在字母顺序中的“cat”和“doggie”之间？ - Bemmu
2
我认为你应该在小数点后面进行十进制数学运算。所以，a->0.01..; aa->0.0101..; z->0.9..; zz->0.99.. - Debilski
1
你可以在字符串末尾添加 'z'：pad = lambda s,a=a,b=b: s.ljust(max(len(a), len(b)), alphabet[-1]) 例如：a,b = [debase(pad(s)) for s in (a,b)]。在这种情况下，“cundeb”位于“cat”和“doggie”之间。 - jfs
为了澄清我为什么认为"budeel"不在字母顺序中的"cat"和"doggie"之间：sorted(["budeel", "cat", "doggie"]) = ['budeel', 'cat', 'doggie'] - Bemmu
不适用于连续字符串，即 average("a", "b") # 返回 'a'。 - Ahmed Fasih
显示剩余6条评论
6
如果您是按字母顺序排序，只需使用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
什么是“debase”和“enbase”？ - Chris Dutrow
@ChrisDutrow，请看@FogleBird的回答。 - John La Rooy
啊，我明白了。我混淆了，以为它是Python库函数，但无论如何都找不到它 :) 谢谢！ - Chris Dutrow
6
听起来您想把字母字符视为介于0和1之间的基数26值。当您有不同长度的字符串（以10为例），例如305和4202时，由于您一次只查看一个字符，因此得出的中点为3。相反，将它们视为浮点数尾数：0.305和0.4202。从那里，很容易得出中点为0.3626（如果您愿意，可以四舍五入）。
对于字母进行类似的操作（a=0...z=25，ba=26，bb=27等）以计算字母：
cat变成'a.cat'，doggie变成'a.doggie'，做数学运算后，cat的十进制值为0.078004096，doggie的值为0.136390697，平均值为0.107197397，在基数26中大约是"cumcqo"。
1
如果字符串长度不同，则最好使用基于27进制，其中0表示“字符不存在于字符串中”，1..26表示字母。 - user287792
通过使用'a'作为0，并使用分数运算，这个问题基本上就解决了。 - Eclipse
2
1

谢谢所有回答的人，但最终我还是自己写了一个解决方案，因为其他的解决方案并不完全符合我的需求。我正在尝试对应用程序引擎键名进行平均值计算，经过进一步研究，我发现它们实际上允许在名称中使用任何7位ASCII字符。此外，我无法完全依赖将键名首先转换为浮点数的解决方案，因为我怀疑浮点数的精度并不足够。

要计算平均值，首先将两个数字相加，然后除以2。这两个操作都非常简单，所以我决定编写函数来添加和除以以列表表示的基数128数字。这个解决方案尚未在我的系统中使用，所以我可能仍然会发现其中一些错误。此外，它可能可以更简洁，但这只是我需要完成的任务，而不是追求完美。

# Given two lists representing a number with one digit left to decimal point and the
# rest after it, for example 1.555 = [1,5,5,5] and 0.235 = [0,2,3,5], returns a similar
# list representing those two numbers added together.
#
def ladd(a, b, base=128):
        i = max(len(a), len(b))
        lsum = [0] * i  
        while i > 1:
                i -= 1
                av = bv = 0
                if i < len(a): av = a[i]
                if i < len(b): bv = b[i]
                lsum[i] += av + bv
                if lsum[i] >= base:
                        lsum[i] -= base
                        lsum[i-1] += 1
        return lsum

# Given a list of digits after the decimal point, returns a new list of digits
# representing that number divided by two.
#
def ldiv2(vals, base=128):
        vs = vals[:]
        vs.append(0)
        i = len(vs)
        while i > 0:
                i -= 1
                if (vs[i] % 2) == 1:
                        vs[i] -= 1
                        vs[i+1] += base / 2
                vs[i] = vs[i] / 2
        if vs[-1] == 0: vs = vs[0:-1]
        return vs

# Given two app engine key names, returns the key name that comes between them.
#
def average(a_kn, b_kn):
        m = lambda x:ord(x)
        a = [0] + map(m, a_kn)
        b = [0] + map(m, b_kn)
        avg = ldiv2(ladd(a, b))
        return "".join(map(lambda x:chr(x), avg[1:]))

print average('a', 'z') # m@
print average('aa', 'zz') # n-@
print average('aa', 'az') # am@
print average('cat', 'doggie') # d(mstr@
print average('google', 'microsoft') # jlim.,7s:
print average('microsoft', 'google') # jlim.,7s:
0
import math
def avg(str1,str2):
    y = ''
    s = 'abcdefghijklmnopqrstuvwxyz'
    for i in range(len(str1)):
        x = s.index(str2[i])+s.index(str1[i])
        x = math.floor(x/2)
        y += s[x]
    return y

print(avg('z','a')) # m
print(avg('aa','az')) # am
print(avg('cat','dog')) # chm

仍在处理长度不同的字符串... 有什么想法吗？

0

这个版本认为 'abc' 是一个像 0.abc 这样的小数。在这种方法中，空格为零且是有效的输入/输出。

MAX_ITER = 10
letters = " abcdefghijklmnopqrstuvwxyz"
def to_double(name):
    d = 0
    for i, ch in enumerate(name):
        idx = letters.index(ch)
        d += idx * len(letters) ** (-i - 1)
    return d

def from_double(d):
    name = ""
    for i in range(MAX_ITER):
        d *= len(letters)
        name += letters[int(d)]
        d -= int(d)
    return name

def avg(w1, w2):
    w1 = to_double(w1)
    w2 = to_double(w2)
    return from_double((w1 + w2) * 0.5)

print avg('a', 'a') # 'a'
print avg('a', 'aa') # 'a mmmmmmmm'
print avg('aa', 'aa') # 'a zzzzzzzz'
print avg('car', 'duck') # 'cxxemmmmmm'

不幸的是，朴素算法无法检测到周期性的“z”，这就像十进制中的0.99999；因此，“a zzzzzzzz”实际上是“aa”（在“z”周期性之前的空格必须增加一个）。

为了使其正常化，您可以使用以下函数

def remove_z_period(name):
    if len(name) != MAX_ITER:
        return name
    if name[-1] != 'z':
        return name
    n = ""
    overflow = True
    for ch in reversed(name):
        if overflow:
            if ch == 'z':
                ch = ' '
            else:
                ch=letters[(letters.index(ch)+1)]
                overflow = False
        n = ch + n
    return n

print remove_z_period('a zzzzzzzz') # 'aa'
0

我已经有一段时间没有用Python编程了，这似乎很有趣，值得一试。 请容忍我的递归编程。太多的函数式语言看起来像Python。

def stravg_half(a, ln):
     # If you have a problem it will probably be in here.
     # The floor of the character's value is 0, but you may want something different
     f = 0
     #f = ord('a')
     L = ln - 1
     if 0 == L:
          return ''
     A = ord(a[0])
     return chr(A/2) + stravg_half( a[1:], L)

def stravg_helper(a, b, ln, x):
    L = ln - 1
    A = ord(a[0])
    B = ord(b[0])
    D = (A + B)/2
    if 0 == L:
        if 0 == x:
             return chr(D)
        # NOTE: The caller of helper makes sure that len(a)>=len(b)
        return chr(D) + stravg_half(a[1:], x)
    return chr(D) + stravg_helper(a[1:], b[1:], L, x)

def stravg(a, b):
    la = len(a)
    lb = len(b)
    if 0 == la:
        if 0 == lb:
            return a # which is empty
        return stravg_half(b, lb)
    if 0 == lb:
        return stravg_half(a, la)
    x = la - lb
    if x > 0:
        return stravg_helper(a, b, lb, x)
    return stravg_helper(b, a, la, -x) # Note the order of the args
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接