Given a finite, partially ordered set with the following two properties:

  1. Every element in the set has one of two types: "A" or "B". The type does not define the total ordering of the set and is metadata.
  2. Every element in the set is a natural number and the poset can be ranked by the numbers themselves. This means that the sorted elements themselves provide one of the possible total orders of the poset, or in graph theory, one of the topological orderings of the DAG.

What is the most optimal algorithm to find the total ordering of the described poset that groups elements with the same type together?

The posets are represented by describing the type and dependencies of every element such that:

0:{[], A}, 1:{[0], A}, 2:{[], B}, 3:{[2], A} 4:{[0], A}, 5:{[0,1,4], B}, 6:{[1,2], A}, 7:{[3,6], A}

looks like this:

Where the blue dot represents the "B" type and every other element is of type "A". The following are some of the valid total orderings:

  1. [0, 1, 2, 3, 4, 5, 6, 7]
  2. [0, 2, 1, 4, 3, 6, 5, 7]
  3. [0, 2, 1, 4, 3, 6, 7, 5]

However, I have been trying to find the most optimal algorithm that will group elements based on their type, if it is possible, while preserving the total order. For the DAG/poset in the example, one of the possible solutions would be:

[[0, 1, 4], [5, 2], [6, 3, 7]]

Thank you!

  • 1
    $\begingroup$ To make this a well-defined optimisation problem, you need to describe how to score a "grouping". E.g., in your example there is 1 group of blue elements and 2 groups of non-blue elements -- is a grouping in which there is just 1 of each kind better? $\endgroup$ – j_random_hacker May 19 '20 at 0:07
  • $\begingroup$ Yes, groupings should only have elements of one kind or the other. There should be as little groupings as possible. It is also preferred, but not required, for blue groupings to come before non-blue groupings if possible. $\endgroup$ – pombo May 19 '20 at 0:56
  • $\begingroup$ Please define "most optimal algorithm". Optimal by what metric? $\endgroup$ – D.W. May 19 '20 at 4:10
  • 1
    $\begingroup$ Please define what you mean by a order "grouping" items together. What are the groups that are defined by a total order? Also you still have not answered @j_random_hacker's question. We need a precise, complete specification of the score that should be assigned to any total order: something that is well-enough specified that we could write an algorithm or a program to compute it, given a candidate total order. $\endgroup$ – D.W. May 19 '20 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.