Предположим, что Вы берете строки и 'z' и перечисляете все строки, которые прибывают между ними в алфавитном порядке: ['b', 'c'... 'x', 'y', 'z']. Возьмите среднюю точку этого списка, и Вы находите 'm'. Таким образом, это отчасти похоже на взятие в среднем те две строки.
Вы могли расширить его до строк больше чем с одним символом, например, средняя точка между 'aa' и 'zz' будет найдена посреди списка ['aa', 'ab', 'ac'... 'zx', 'zy', 'zz'].
Мог бы быть метод Python где-нибудь, который делает это? В противном случае даже знание названия алгоритма помогло бы.
Я начал делать свою собственную стандартную программу, которая просто проходит обе строки и находит среднюю точку первой отличающейся буквы, которая, казалось, работала отлично в этом, средняя точка 'aa' и 'азимута' была '', но затем она перестала работать на 'кошке', средняя точка 'собачки', которая она думает, является 'c'. Я пытался гуглить для "строковой средней точки двоичного поиска" и т.д., но не зная название того, что я пытаюсь сделать здесь, у меня было мало удачи.
Я добавил свое собственное решение как ответ
Если вы определяете алфавит из символов, вы можете просто преобразовать его в основание 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
Если вы имеете в виду в алфавитном порядке, просто используйте алгоритм 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
В этой версии "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'
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
Все еще работаете над строками разной длины ... есть идеи?
Судя по предложенному вами использованию, последовательное хеширование ( http://en.wikipedia.org/wiki/Consistent_hashing ) кажется более разумным.
Я давно не программировал на 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
Похоже, вы хотите рассматривать алфавитные символы как значение base-26 от 0 до 1. Когда у вас есть строки разной длины ( пример в базе 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
Спасибо всем, кто ответил, но в итоге я написал свое собственное решение, потому что другие не совсем то, что мне нужно. Я пытаюсь усреднить имена ключей движка приложений, и, изучив их еще немного, я обнаружил, что они действительно допускают любые 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: