Алгоритм для поддержания «упорядочивающей строки» для упорядочения элементов базы данных

Question

У меня есть база данных, в которой я хотел бы сохранить произвольное упорядочение для определенного элемента. База данных, о которой идет речь, не поддерживает наборы заказов, поэтому я должен сделать это сам.

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

Item A - Position 1 
Item B - Position 1.5 (just inserted). 
Item C - Position 2 

Теперь, для различных причины, по которым я не хочу использовать float, я бы хотел использовать строки. Например:

Item A - Position a 
Item B - Position aa (just inserted). 
Item C - Position b 

Я хотел бы сохранить эти строки как можно короче, так как они никогда не будут «прибраться».

Может ли кто-нибудь предложить алгоритм для генерации такой строки как можно более эффективно и компактно?

Спасибо,

Tim

Answer 1

Было бы разумно назначить позицию «am» или «a» позиции B и использовать бинарные деления для других вставок. Это напоминает систему чисел 26-al, где символы 'a' .. 'z' соответствуют 0..25.

a b //0 1 
a an b //insert after a - middle letter of alphabet 
a an au b //insert after an 
a an ar au b //insert after an again (middle of an, au) 
a an ap ar au b //insert after an again 
a an ao ap ar au b //insert after an again 
a an ann ao... //insert after an, there are no more place after an, have to use 3--symbol label 
.... 
a an anb... //to insert after an, we treat it as ana 
a an anan anb // it looks like 0 0.5 0.505 0.51 

псевдокод для бинарной структуры дерева:

function InsertAndGetStringKey(Root, Element): string 
    if Root = nil then 
    return Middle('a', 'z') //'n' 

    if Element > Root then 
    if Root.Right = nil then 
     return Middle(Root.StringKey, 'z') 
    else 
     return InsertAndGetStringKey(Root.Right, Element) 

    if Element < Root then 
    if Root.Left = nil then 
     return Middle(Root.StringKey, 'a') 
    else 
     return InsertAndGetStringKey(Root.Left, Element) 

Middle(x, y): 
    //equalize length of strings like (an, anf)-> (ana, anf) 
    L = Length(x) - Length(y) 
    if L < 0 then 
    x = x + StringOf('a', -L) //x + 'aaaaa...' L times 
    else if L > 0 then 
    y = y + StringOf('a', L) 

    if LL = LastSymbol(x) - LastSymbol(y) = +-1 then 
    return(Min(x, y) + 'n') // (anf, ang) - > anfn 
    else 
    return(Min(x, y) + (LastSymbol(x) + LastSymbol(y))/2) // (nf, ni)-> ng 

Answer 2

Как указано проблема не имеет решения. Как только алгоритм генерирует строки «a» и «aa» для смежных элементов, между ними не может быть вставлена ​​строка. Это является фатальной проблемой для подхода. Эта проблема не зависит от алфавита, используемого для строк: замените «a» на «первую букву в алфавите, который вы используете», если хотите.

Конечно, его можно обойти, изменив строку упорядочения для других элементов, когда этот тупик достигнут, но это, кажется, находится за пределами того, чего хочет OP.

Я думаю, что проблема эквивалентна поиску целого числа для представления порядка элемента и нахождения того, что, например, 35 и 36 уже используются для упорядочения существующих элементов. Просто нет целых чисел от 35 до 36, независимо от того, насколько сильно вы смотрите.

Используйте действительные числа или приближение компьютера, такие как числа с плавающей запятой или рациональные значения.

РЕДАКТИРОВАТЬ в ответ на комментарий OP в

Просто адаптировать алгоритм для добавления 2: рациональные (A/B) + (C/D) = (Ad + Cb)/BD. Возьмите (ad + cb)/2 (округление, если вы хотите или хотите), и у вас есть разумный промежуток между первыми двумя.

Answer 3

ли капители вариант?

Если это так, я бы использовал их для вставки между смежными смежными значениями.

Например, чтобы вставить между аа

Вы можете сделать:

< AAAA --- эта шапка. говорит, что есть еще одно место между соседними небольшими значениями .ie. а [Aa]

AABA

AACA

ABAA

ABBA

аа

Теперь, если вам нужно вставить между а и AAAA

Вы могли бы do

a

aAAaaa < --- 2 крышки. рассказывает есть еще два места между соседними малыми значениями т.е. [AAAA]

aAAaba

aAAaca

...

aAAbaa

AAAA

С точки зрения будучи компактным или эффективным, я не делаю никаких претензий ...