0

我有一个数据库，我想在其中存储特定元素的任意顺序。有问题的数据库不支持订单集，所以我必须自己做。

一种方法是存储元素位置的浮点值，然后在插入新元素时取周围元素位置的平均值：

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 并使用二进制除法步骤进行另一个插入是合理的。这类似于 26 位数字系统，其中 '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
于 2012-06-07T09:10:14.933 回答
0

如前所述，问题没有解决方案。一旦算法为相邻元素生成了字符串“a”和“aa”，就没有可以在它们之间插入的字符串。这是该方法的致命问题。此问题与用于字符串的字母表无关：如果您愿意，请将“a”替换为“使用的字母表中的第一个字母”。

当然，当陷入僵局时，可以通过更改其他元素的排序字符串来解决它，但这似乎超出了 OP 的要求。

我认为这个问题相当于找到一个整数来表示一个元素的顺序，然后发现 35 和 36 已经用于对现有元素进行排序。35 到 36 之间根本没有整数，不管你怎么看。

使用实数或计算机近似值，例如浮点数或有理数。

编辑以回应OP的评论

只需调整算法以添加 2 个有理数：(a/b)+(c/d) = (ad+cb)/bd。取 (ad+cb)/2 （如果你想要或需要四舍五入），你在前两者之间有一个合理的中间值。

于 2012-06-07T08:54:59.823 回答
0

资本是一种选择吗？

如果是这样，我会使用它们在其他相邻值之间插入。

例如插入 aaa 之间

你可以这样做：

一种

aAaa <--- 这个上限。告诉相邻的小值之间还有一个位置。即。一个[Aa]a

氨基酸

aAca

咩咩

阿巴

啊

现在，如果您需要在 a 和 aAaa 之间插入

你可以做

一种

aAAAaa <--- 2 个大写字母。表示相邻的小值之间还有两个位置，即 a[AAaa]a

啊啊啊啊

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

...

啊啊啊

啊啊啊

就紧凑或高效而言，我没有任何要求......

于 2012-06-07T10:15:23.490 回答