0

特定の要素の任意の順序を格納したいデータベースがあります。問題のデータベースは注文セットをサポートしていないため、自分で行う必要があります。

これを行う 1 つの方法は、要素の位置に float 値を格納し、新しい要素を挿入するときに周囲の要素の位置の平均を取ることです。

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

さて、さまざまな理由から、フロートを使用したくないので、代わりに文字列を使用したいと思います。例えば：

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

これらの文字列は「整理」されないため、できるだけ短くしたいと思います。

このような文字列をできるだけ効率的かつコンパクトに生成するためのアルゴリズムを提案できる人はいますか?

ありがとう、

ティム

4

3 に答える 3

1

'am' または 'an' の位置をアイテム B に割り当て、別の挿入には 2 分割ステップを使用するのが合理的です。これは、'a'..'z' 記号が 0..25 に対応する 26-al 番号システムに似ています。

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
于 2012-06-07T09:10:14.933 に答える
0

述べたように、問題には解決策がありません。アルゴリズムが隣接する要素の文字列「a」と「aa」を生成すると、それらの間に挿入できる文字列はありません。これはアプローチにとって致命的な問題です。この問題は、文字列に使用されるアルファベットとは無関係です。必要に応じて、「a」を「使用されるアルファベットの最初の文字」に置き換えます。

もちろん、この行き詰まりに達したときに他の要素の順序文字列を変更することで回避できますが、それはOPが望んでいることを超えているようです。

この問題は、要素の順序を表す整数を見つけて、たとえば35と36が既存の要素の順序にすでに使用されていることを見つけることと同じだと思います。どんなに一生懸命見ても、35から36の間に整数はありません。

実数、または浮動小数点数などのコンピューター近似、または有理数を使用します。

OPのコメントに応じて編集

（a / b）+（c / d）=（ad + cb）/bdの2つの有理数を追加するためにアルゴリズムを適応させるだけです。（ad + cb）/ 2（必要または必要な場合は丸め）を取ると、最初の2つの中間に合理的な値があります。

于 2012-06-07T08:54:59.823 に答える
0

大文字はオプションですか？

もしそうなら、それらを使用して、隣接する値の間に挿入します。

たとえば、 aa の間に挿入するには

あなたがすることができます：

a

aAaa <--- このキャップ。隣接する小さな値の間にもう 1 つの場所があることを示します。あ[あ]あ

アバ

アアカ

あばあ

アバ

ああ

a と aAaa の間に挿入する必要がある場合

あなたができる

a

aAAAaaa <--- 2 キャップ。隣接する小さな値の間にさらに 2 つの場所があることを示します。つまり、a[AAaa]a

あああああ

あああああ

...

あああああ

ああああ

コンパクトまたは効率的であるという点では、私は主張しません...

于 2012-06-07T10:15:23.490 に答える