3
$\begingroup$

I have a totally ordered set S and I'd like to re-order it based on a partial ordering P.

If set S looks like [A, B, C, D, E] where A < B, B < C, and so on. And set P looks like [A, E, B]. Then I'd like to create a new ordered set S' with ordering [A, E, B, C, D].

The idea being that S' is based on S, with minimal changes made in order to make it conform to the new ordered relationships introduced by P. If P had been [E, B, A], then S' could be [E, B, A, C, D] or [C, D, E, B, A], but the first would be preferred because it preserves more of the original ordered relationships than the latter (5: B < C, B < D, A < C, A < D, C < D) vs (3: C < D, C < E, D < E).

Is there an efficient algorithm that does this? Or any area of research I could look into?

$\endgroup$
4
  • 1
    $\begingroup$ Are only two ways of completing $P $ allowed? I mean, can we write the remaining items only all on the left or all on the right of $P $? Or can we distribute them some on the left and some on the right to find the best pattern? $\endgroup$
    – Anatoly
    Commented Oct 8, 2016 at 14:57
  • $\begingroup$ There are possibly several way of completing $P$. You could distribute items before, in-between, and/or after the elements of $P$ to complete the ordering. I had actually not been thinking of that approach (start with the partial ordering, then add items from the original set), I had been thinking of starting with the original set and altering it until it satisfied the partial ordering. $\endgroup$
    – onlynone
    Commented Oct 11, 2016 at 15:06
  • $\begingroup$ So I've got a solution based on @Anatoly's suggestion, but I don't think it's very efficient. It basically starts $P'$ as a copy of $P$. Then iterates through each element ($i$) of $S$ that isn't in $P$, finding the location in $P'$ that maximizes the number of consistent relationships for $i$. Then it inserts $i$ into $P'$ at that location and repeats for the next element $i$ from $S$. $\endgroup$
    – onlynone
    Commented Oct 11, 2016 at 16:35
  • $\begingroup$ @onlynone It is not that bad, is it? It is still in $O(|S|)$ for the worst case. which is typical of sorting. A small optimization could be to notice that if $B$ is a direct successor of $A$ (in $S$) and you already found the optimal location for $A$ then the optimal location for $B$ is right after $A$. $\endgroup$
    – wece
    Commented Oct 13, 2016 at 8:56

1 Answer 1

Reset to default
1
+50
$\begingroup$
  1. Do some pair wise comparisons between consecutive members of the new partial ordering. In this case, you would first compare $E$ and $B$.
  2. If the new partial order is the same as the original one, do nothing. If they are different, then you have two options, you could either take the now lower one and put it below the now higher one (i.e. Putting $E$ below $B$ and keeping $B$ in the same spot) or you can take the now higher one and put it above the now lower one (i.e. Putting $B$ above $E$ and keeping $E$ in the same spot). You can check how many relationships that affects to determine what to do.
  3. All the elements you have moved so far ($E$ and $B$) are now grouped together. There is absolutely no way that any element can be put between them and achieve an optimal new ordering. If you had $B<E$ in your new partial ordering, you would not group them together. For the rest of the algorithm, $E$ and $B$ are consecutive elements and are moved together, period.
  4. Repeat until you move through the entirety of $P$.
$\endgroup$
6
  • $\begingroup$ I kinda like the solution hinted at by @Anatoly, but since this is the only answer. I'll go ahead and select this one for now. $\endgroup$
    – onlynone
    Commented Oct 13, 2016 at 21:42
  • $\begingroup$ If you see any possible problems with this, feel free to comment. $\endgroup$
    – AlgorithmsX
    Commented Oct 13, 2016 at 23:44
  • $\begingroup$ No specific problems, I'm just thinking from an algorithmic standpoint how efficient it is vs the approach of starting with the partial ordering and inserting elements from the original set. $\endgroup$
    – onlynone
    Commented Oct 14, 2016 at 14:11
  • $\begingroup$ With this approach, you end up moving large sequences of elements together. For example: if you move E before B, then later decide that B should be moved after D, you have to move E and B together after D. Similarly, if later you need to put some element before B, you actually have to put it (and any others it's attached to) prior to D. It just leads to lots of element swapping. $\endgroup$
    – onlynone
    Commented Oct 14, 2016 at 14:22
  • $\begingroup$ Although I do see that, I believe that this does get you the optimal solution. You might get away with creating an empty set with the same size as the original partial ordering and copying new elements there. $\endgroup$
    – AlgorithmsX
    Commented Oct 14, 2016 at 16:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .