Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: LineSort
Date: Tue, 10 Jun 2025 07:51:06 +0100
Organization: Fix this later
Lines: 36
Message-ID: <1028kkq$13aji$2@dont-email.me>
References: <1027gln$ofnf$1@dont-email.me> <1027i1m$avr$1@news.muc.de>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 10 Jun 2025 08:51:06 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="b160597973678a50bbd47b6c9288997b";
	logging-data="1157746"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+P6jrVHbDqCUai8WNyK2a+eAJYEanCt9nWHXCGaxrU2Q=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:HvdF8rRAXMe6ePZOxXvapf+8cOE=
In-Reply-To: <1027i1m$avr$1@news.muc.de>
Content-Language: en-GB

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