Richard Heathfield <rjh@cpax.org.uk> 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.

This sounds like something called a "topological sort", where there are
lots of ordering relationships between pairs of objects and the object is
to reach a total ordering of all the objects such that each of the given
pairs is in the correct order.

The standard application of this is in make utilities where there are
lots of "depends upon" relationships expressed in the Makefile.

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 suspect if you search the Internet for "topological sort", you'll find everything you want to know (if not a lot more).

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

--
Alan Mackenzie (Nuremberg, Germany).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Am Mon, 09 Jun 2025 21:37:08 +0100 schrieb Richard Heathfield:

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

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.

Which application does this arise from?

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.

Looks a lot like bubblesort, a well-known quadratic algorithm.

--
Am Sat, 20 Jul 2024 12:35:31 +0000 schrieb WM in sci.math:
It is not guaranteed that n+1 exists for every n.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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?

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 09/06/2025 21:48, joes wrote:

Am Mon, 09 Jun 2025 21:37:08 +0100 schrieb Richard Heathfield:

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

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.

Which application does this arise from?

brainbashers.com :-)

Jill finished after Helen but beat Alan. Bob lost out to Derek
but was faster than Tina... etc etc etc.

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.

Looks a lot like bubblesort, a well-known quadratic algorithm.

Yes, it certainly has the bubbling quality from which bubblesort
gets its name, but bubblesort is allowed to compare two arbitrary
items directly, which is not possible here.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 9 Jun 2025 16:33:03 -0600
Jeff Barnett <jbb@notatt.com> wrote:

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.

The Doctor's a Job's worth?


--
Bah, and indeed Humbug.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)