Среднее из двух строк в алфавитном/лексикографическом порядке

Question

Предположим, что вы берете строки 'a' и 'z' и перечисляете все строки, которые находятся между ними в алфавитном порядке: ['a', 'b', 'c'. .. 'x', 'y', 'z']. Возьмите середину этого списка, и вы найдете «m». Так что это похоже на то, чтобы взять в среднем эти две строки.

Вы можете расширить его до строк с более чем одним символом, например, средняя точка между 'aa' и 'zz' будет найдена в середине списка ['aa', 'ab', 'ac'. .. 'zx', 'zy', 'zz'].

Может ли быть где-нибудь метод Python, который это делает? Если нет, даже знание названия алгоритма поможет.

Я начал создавать свою собственную рутину, которая просто проходит через обе строки и находит середину первой различной буквы, которая, казалось, отлично работает в том, что «aa» и «az» были «am», но тогда это не получается на «cat», «doggie» midpoint, который он считает «c». Я попробовал Googling для «бинарной строки поисковой строки» и т. Д., Но не зная названия того, что я пытаюсь сделать здесь, мне не повезло.

Я добавил свое собственное решение, как ответ

Answer 1

Если определить алфавит символов, вы можете просто преобразовать в базу 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 

Редактировать: на основе комментариев и другие ответы, вы можете обрабатывать строки различной длины путем добавления первой буквы алфавита на более короткие слова, пока они не одинаковой длины. Это приведет к «среднему» падению между двумя входами в лексикографическом роде. Изменения кода и новые выходы ниже.

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

на основе предлагаемого вами использования, в соответствии хеширования (http://en.wikipedia.org/wiki/Consistent_hashing), кажется, больше смысла.

Answer 3

Похоже на то, что вы хотите, - обрабатывать алфавитные символы как значение base-26 между 0 и 1. Если у вас есть строки разной длины (пример в базе 10), скажем, 305 и 4202, ваше выступление с серединой 3, так как вы смотрите на персонажей по одному. Вместо этого обрабатывайте их как мантисса с плавающей запятой: 0.305 и 0.4202. Из этого легко подытожить середину 0,3626 (вы можете округлить, если хотите).

Сделайте то же самое с основанием 26 (а = 0 ... г = 25, Ьа = 26, бб = 27 и т.д.), чтобы сделать расчеты для писем:

кошка становится 'a.cat' и собачки становится «a.doggie», делает математику дает кошке десятичное значение 0.078004096, собачки значение 0.136390697, со средним числом 0.107197397, который в базе 26 примерно «cumcqo»

Answer 4

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 

Все еще работает над струны разной длины ... любые идеи?

Answer 5

Если вы имеете в виду алфавитную форму, просто используйте алгоритм 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 6

Эта версия думает 'а' представляет собой дробь, как 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' 

К сожалению, наивный алгоритм не в состоянии обнаружить, это будет что-то периодической «Заболоцкого как 0.99999 в десятичной системе; Поэтому «а zzzzzzzz» на самом деле «аа» (пространство перед «г» периодичность должна быть увеличена на единицу.

Для того, чтобы нормализовать это, вы можете использовать следующую функцию

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' 

Answer 7

убежище I «т запрограммирован в питоне в то время, и это, казалось, достаточно интересно попробовать. медведя с моим рекурсивным программированием. Слишком много функциональных языков выглядеть питон.

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 

Answer 8

Спасибо всем, кто ответил, но я в конечном итоге писать свой собственное решение, потому что rs не совсем то, что мне нужно. Я пытаюсь усреднить имена ключевых слов ядра приложения, и после изучения их немного больше, я обнаружил, что они фактически разрешают любые 7-битные символы ASCII в именах. Кроме того, я не мог положиться на решения, которые сначала конвертировали имена ключей в плавающие точки, потому что я подозревал, что точность с плавающей запятой просто недостаточна.

Чтобы взять среднее значение, сначала вы добавляете два числа вместе, а затем делитесь на два. Это и такие простые операции, что я решил просто сделать функции для добавления и разделения базовых 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: