Re: LineSort

On 09/06/2025 22:00, Alan Mackenzie wrote:

Richard Heathfield <rjh@cpax.org.uk> wrote:

<snip>

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.

 This sounds like something called a "topological sort"

...and turns out to be exactly that. You have saved me from having to write a paper, so I can thank you for that, and hopefully I have at least been able to produce a few moments of distraction away from /the/ dominant topic.
<snip>

Any ideas?

 I suspect if you search the Internet for "topological sort", you'll find
everything you want to know (if not a lot more).

Considerably more :-)
but at least now I know.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within