Sorting with only a partial order definition
Lasse Vågsæther Karlsen
lasse at vkarlsen.no
Thu Oct 27 12:08:38 CEST 2005
Lasse Vågsæther Karlsen wrote:
> Paul Rubin wrote:
>> Lasse Vågsæther Karlsen <lasse at vkarlsen.no> writes:
>>> I have a list of items and a "rule" for ordering them.
Ok, managed to implement the algorithm. Might not be the optimal
solution (memory and speed-wise) but it worked and doesn't take too long
to run either so I'm going to stick with it.
I have a different question though, along the same lines, but one that
doesn't need a solution, just want to know if something like it exists.
A while back I had an application that had a lot of items that it needed
to order. The problem, however, was that the rules was not defined at
all. Instead it was opted for a visual solution where the user would be
presented with images and had to rearrange them in the order that was
necessary. The application was one I helped build for a friend which
combined images from several cameras and allowed him to sort them
according to the contents so that he could get a timeline formed.
The date/time stamps on the cameras was not directly usable for various
reasons so the visual ordering was what we ended up on. For instance,
two of the cameras was not digital ones so they had no timestamp except
for the one provided by the scanning software.
In that application we talked about presenting the user with two and two
images and he just had to click on the image that came first. The
problem with this was to try to present the "right" images to the user
so that he had to minimize the number of clicks.
In other words, try to pick nodes in the graph and ask the user to
provide the direction of the edge, and the "picking algorithm" would
work in such a way that the number of edges would be minimized.
Not sure if I'm explaining it correctly.
The solution we ended up with was to present the user with all the
images in one big timeline and just let him drag them around. This worked.
What I was wondering about is if there is an algorithm that would do
what I want? Ie. help me pick the nodes so as to minimize the number of
edges. Obviously the answer to the first pair of nodes will influence
which nodes will be subsequently picked, so each answer would stear the
algorithm in a way, not just go into the final problem.
If anyone got the name of such an algorithm or something I would like to
look at it at least. Application is built and deployed so I'm not
looking for a solution to implement.
Lasse Vågsæther Karlsen
mailto:lasse at vkarlsen.no
PGP KeyID: 0x2A42A1C2
More information about the Python-list