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
- 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.