The problem statement is that there is a array with indices 1 to k which each contain a list that ranks l of n total items via order (i.e. list 1-2-3-4 is equivalent to 1>2>3>4). Is it possible to convert this array into an adjacency list where the vertices are the n items and any edge represents the relationship (u,v) = u > v. If it is useful n is known and the given lists can be treated as arraylists. Any help is greatly appreciated.
I have tried to formulate a solution, but every method I can think of either creates many repeat edges, which I can not expect, or requries O(kl^2) time to check each element in a list against those following it.
Edit: Sorry, for the late reply. I have added more information as requested.
-Example: If given
A[1] = 1 - 2 - 4,
A[2] = 5 - 2 - 3, and
A[3] = 1 - 4 - 3
then the algorithm should produce an adjacency list X defined as follows
X[1] = 2 - 4 -3,
X[2] = 4 - 3,
X[3] = empty,
X[4] = 3, and
X[5] = 2 - 3
- The number of redundancies only has to be low enough that it is less than kl, as its later need for a graph algorithm to execute in O(kl + n) time.
I have found an answer to my own question by avoiding solving it. In this, case the full ordinal rankings do not need to be expressed as edges. It is possible to not lose information just by recording the element ranked directly below an element. I.e. we don't need the edges of a vertex to be all vertices it's ranked above, we just need the edge to the highest-ranked vertex it's ahead of.