Average Of Two Strings In Alphabetical/lexicographical Order

September 28, 2022 Post a Comment

Suppose you take the strings 'a' and 'z' and list all the strings that come between them in alphabetical order: ['a','b','c' ... 'x','y','z']. Take the midpoint of this list and yo

Solution 1:

If you define an alphabet of characters, you can just convert to base 10, do an average, and convert back to base-N where N is the size of the alphabet.

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: Based on comments and other answers, you might want to handle strings of different lengths by appending the first letter of the alphabet to the shorter word until they're the same length. This will result in the "average" falling between the two inputs in a lexicographical sort. Code changes and new outputs below.

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

Solution 2:

If you mean the alphabetically, simply use FogleBird's algorithm but reverse the parameters and the result!

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

or rewriting average like so

>>> 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

Solution 3:

It sounds like what you want, is to treat alphabetical characters as a base-26 value between 0 and 1. When you have strings of different length (an example in base 10), say 305 and 4202, your coming out with a midpoint of 3, since you're looking at the characters one at a time. Instead, treat them as a floating point mantissa: 0.305 and 0.4202. From that, it's easy to come up with a midpoint of .3626 (you can round if you'd like).

Do the same with base 26 (a=0...z=25, ba=26, bb=27, etc.) to do the calculations for letters:

cat becomes 'a.cat' and doggie becomes 'a.doggie', doing the math gives cat a decimal value of 0.078004096, doggie a value of 0.136390697, with an average of 0.107197397 which in base 26 is roughly "cumcqo"

Solution 4:

Based on your proposed usage, consistent hashing ( http://en.wikipedia.org/wiki/Consistent_hashing ) seems to make more sense.

Solution 5:

Thanks for everyone who answered, but I ended up writing my own solution because the others weren't exactly what I needed. I am trying to average app engine key names, and after studying them a bit more I discovered they actually allow any 7-bit ASCII characters in the names. Additionally I couldn't really rely on the solutions that converted the key names first to floating point, because I suspected floating point accuracy just isn't enough.

To take an average, first you add two numbers together and then divide by two. These are both such simple operations that I decided to just make functions to add and divide base 128 numbers represented as lists. This solution hasn't been used in my system yet so I might still find some bugs in it. Also it could probably be a lot shorter, but this is just something I needed to get done instead of trying to make it perfect.

# 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:

Python Manual