CODEWITHSUNDEEP
databasealgorithmgoogle-app-engine
tarmes
tarmes

Reputation: 15442

Algorithm for maintaining an "ordering string" for ordering database elements

I have a database in which I'd like to store an arbitrary ordering for a particular element. The database in question doesn't support order sets, so I have to do this myself.

One way to do this would be to store a float value for the element's position, and then take the average of the position of the surrounding elements when inserting a new one:

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

Now, for various reasons I don't wish to use floats, I'd like to use strings instead. For example:

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

I'd like to keep these strings as short as possible since they will never be "tidied up".

Can anyone suggest an algorithm for generating such string as efficiently and compactly as possible?

Thanks,

Tim

Upvotes: 0

Views: 175

Answers (3)

MBo
MBo

Reputation: 80232

It would be reasonable to assign 'am' or 'an' position to Item B and use binary division steps for another insertions. This resembles 26-al number system, where 'a'..'z' symbols correspond to 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

Pseudocode for binary tree structure:

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

Upvotes: 1

user1258245
user1258245

Reputation: 3639

Are capitals an option?

If so, I would use them to insert between otherwise adjacent values.

For instance to insert between a aa

You could do:

a

aAaa <--- this cap. tells there is one more place between adjacent small values .ie. a[Aa]a

aAba

aAca

aBaa

aBba

aa

Now if you need to insert between a and aAaa

You could do

a

aAAaaa <--- 2 caps. tells there are two more places between adjacent small values i.e. a[AAaa]a

aAAaba

aAAaca

...

aAAbaa

aAaa

In terms of being compact or efficient I make no claims...

Upvotes: 0

High Performance Mark
High Performance Mark

Reputation: 78334

As stated the problem has no solution. Once an algorithm has generated strings 'a' and 'aa' for adjacent elements there is no string which can be inserted between them. This is a fatal problem for the approach. This problem is independent of the alphabet used for the strings: replace 'a' by 'the first letter in the alphabet used' if you wish.

Of course, it can be worked around by changing the ordering string for other elements when this impasse is reached, but that seems to be beyond what OP wants.

I think that the problem is equivalent to finding an integer to represent the order of an element and finding that, say, 35 and 36 are already used to order existing elements. There is simply no integer between 35 and 36, no matter how hard you look.

Use real numbers, or a computer approximation such as floating-point numbers, or rationals.

EDIT in response to OP's comment

Just adapt the algorithm for adding 2 rationals: (a/b)+(c/d) = (ad+cb)/bd. Take (ad+cb)/2 (rounding if you want or need) and you have a rational midway between the first two.

Upvotes: 0

Related Questions