Re: LineSort

On 6/9/2025 2:37 PM, Richard Heathfield wrote:

I have no doubt that I am not the first one here to reinvent several wheels (my biggest wheel was AVL tree-balancing, but it's by no means the only one).
 So, if a Web search turns nothing up, how does one know that one has been beaten to the punch?
 One asks around, of course... so I'm asking.
 Consider a set of n unequal items, such that EITHER Charles > Lisa OR Lisa > Charles. You are NOT ABLE to compare two items directly, but you are given enough ordered pairings that you can reconstruct the proper order of the set.
 I devised a solution ('LineSort') for this problem, and my question is simply whether prior art beat me to it.
 Place the items in arbitrary order. Starting at the back B, work through the pairings looking for an item A that is currently ahead of B but belongs somewhere behind it, and do this:
 1. cdefAghijkB
 2. cdef_ghijkB
 3. cdefghijkB_
 4. cdefghijkBA
 Keep going through all your pairings, looking for an item that you can dislodge because it belongs behind B; everybody (back to B) shuffles up one place, and the dislodged item goes in the place that B vacates.
 When you've run out of pairings, go round again, this time starting with the item in front of B.
 Once you're starting at the front, obviously you have to stop. That's one pass.
 Make as many passes as you need to until no movements occur throughout the pass.
 Clearly this is fairly easy to de-pessimise, but my question is whether there is prior art for the general approach.
 Any ideas?

I believe the paper "Combining Opinions About the Order of Rule Execution" has a similar algorithm in it. You can snag a copy at
     https://notatt.com/rule-ordering.pdf
The problem approximately solved therein has ordering votes between some or all pairs of elements. You want to find an order on all elements that maximizes the sum of votes consistent with the order minus votes inconsistent with the order. It turns out that this is the weighted feedback edge-set problem know to be NP complete. In other words, if this is your problem you must make do with an approximate optimal unless you have the patients of Job.
--
Jeff Barnett