Generate a new total ordered set from an existing ordered set and a partial ordering

Question

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?

Answer 1

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