How to sort a set when elements have multiple relationships with each other

Question

I am looking for an algorithm to do some sort of advanced sorting of arrays when relations between elements can contradict each other.

so we have a set of I (items) consisting of n elements i1 ... in

There is a set of R (relations) consisting of relations m defined between elements in I

relations can contradict each other, so, for example, one relationship says that A>B , and the other A<B .

eg.

 r1:i1<i35 r2:i100<i4 ... rm:i45>i3 

usually r and m (sizes of sets) can be any positive integers.

the task is to sort I , so the elements go in such a way that preferably the lower ones (based on relations) go to higher ones ... p>

I am looking for an algorithm that will sort the set so that it is as close as possible to the "optimal" order. I assume that to solve such problems there should be a well-known algorithm.

Thanks!

Answer 1

I think that the most reasonable way to measure the quality of a particular order is the amount of relationship data that it violates. If you decide to use this measure, the problem will be equivalent to the (minimal) Arc Arc Arc . Unfortunately, this problem is NP-hard, so there is no efficient (polynomial-time) algorithm.

In the task “Feedback task” you were given a directed graph and asked to find a set of edges of the minimum size, which, if deleted, will destroy all cycles in the graph.

To see how this fits your problem, note that we can represent each element as a vertex in a graph, and each relation as a directed edge between two vertices (indicating, say, a smaller one). There is a conflict if and only if there is a cycle on this graph, i.e. If there is an ordered list of two or more different vertices v_1, v_2, ..., v_k, such that v_i <v_ (i + 1) for all i <k, and also v_k <v_1. It is impossible to order these k vertices without violating at least one constraint. And vice versa, if there is no cycle, i.e. If a graph is a <a hcf = "https://en.wikipedia.org/wiki/Directed_acyclic_graph"> directed acyclic graph, then topological sorting can quickly (in linear time) find a real order that does not violate restrictions. Thus, the size of the feedback arc set is the smallest number of edges that must be removed in order to get a graph that can be ordered without breaking any restriction - or, which is the same, the smallest number of edges that must be broken in any ordering.