1
$\begingroup$

This may be a known problem, with known approaches, but I can't find the right way to search for it.

I would like to name points along a line of unknown final length such that their name reflects their relative position to all other named points on that line. One should be able to insert an arbitrary number of names at any point along the line including outside the existing first and last named points. A lexicographical sort of the point names would always result in a list of points in a monotonic order.

An order of magnitude estimate of the total number of points to be ultimately named can be supplied up front

Additional restrictions:

  • Names must be stable, no-renaming after initial assignment
  • Names may be constructed from a limited character set: 25 lowercase letters a-z with 'L' removed.
  • The naming scheme should not require an extreme fan-out of name length when adding names either outside the existing points or between two adjacent points. E.g. Imagine that I want to add something before the name 'a', that wouldn't be possible while maintaining linear order during sorting. Starting with 'b' only delays the issue. Same for z on the other end.
    • Names should be of the shortest possible length such that a human could easily glance at one and then write it out elsewhere for most names.

It is highly likely that one would want to insert names between previously adjacent names, and then later between adjacent named points in that previous insertion.

The real-life use case for this is the creation of spatial names for all features of a given kind, say genes, in a species when we don't know in advance the total set of features. This is because different individuals only contain a subset of the total sequence space that the whole population of organisms encompass. The problem is easy to solve with static sets of sequences, but not if you allow them to expand at any point along the line (chromosomes) with the addition of new information. The set sizes of interest encompass 10^5 -10^7 items.

$\endgroup$
  • $\begingroup$ It's not clear what the operations are. It appears you want some dynamic data structure, but what operations can be performed on the data structure? When you insert a name at any point on the line, how is the position on the line specified? Probably the answer will be something along the lines of "interpret the position as a real number in the range $[0,1]$, stored in fixed-point, and convert to base 25" or "build a tree with branching factor $\le 25$", but it's hard for me to tell exactly what to suggest since the requirements aren't entirely clear to me. $\endgroup$ – D.W. Jan 26 '18 at 23:15
  • 2
    $\begingroup$ Interpreted literally, this isn't possible. The lexicographic order has no infinitely descending chains and that means that, however you choose to allocate labels, you'll run out of labels to the left if you get a long enough sequence of "And now add another point to the left of everything you already have" instructions. No such problem exists on the right, since you can always follow 'z' with 'zz', 'zzz', 'zzzz', etc. $\endgroup$ – David Richerby Jan 26 '18 at 23:25
2
$\begingroup$

As David points out in a comment, you are asking for an impossible thing because the lexiocgraphic order does not have infinite descending chains, and so you will run out of names if you keep adding points on the far left side. So forget the lexicographic order. (You may keep it if you have an upfront upper bound on the number of points.)

You can use the naming scheme x_N_M where N and M are numbers. Think of this as indexing a point with the fraction N/M. Because fractions are dense, you will never run out of them. To insert a new point on the left of the leftmost point x_N_M, name the new point x_N_2M. To insert on the right of the rightmost point x_U_V name the new point x_2U_V. And to insert between adjacent points x_A_B and x_C_D, name the new point x_E_F where E/F is the average of A/B and C/D.

$\endgroup$
-1
$\begingroup$

No way.

Let's say you have n possible names. I insert the first point into the list, and you name it. However you name it, either there are only $n/2$ possible names larger or only $n/2$ possible names smaller than the name you chose.

I insert the second point so that it is in the range with fewer names. You name it. Now you have at least one range with only $n/4$ possible names. I insert the third point into the range with fewer possible names, and so on. After inserting k points, there will be a range where you have only $n/2^k$ possible names, and I can make you fail when $k ≥ \log n$.

(I actually ran into an implementation of this in some widely shipping software a few years ago, and users did systematically create this situation where it failed, so I had to add some rather horrid code that would at some point rename everything).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.