Reordering list items so that consecutive items replace each other?

Question

Given a list of elements l of size n and a given predicate succeeds(i1,i2) , which returns true if i2 succeeds i1 , what is the best algorithm for reordering elements l such that for all elements i in l, succeeds(i,i.next) returns true?

Answer 1

If only one element can succeed in each element , then this problem can be solved in quadric time.

It actually mimics the creation of a linked list from data and returns it as an array. The bottleneck for each item is which item follows it.

Pseudo Code:

 specialSort(array,n) create an array a of size n for each i from 0 to n: find j such that succeeds(array[i],array[j]) == true //this may require linear search, so it is O(n) if there is such j: a[i] = j else: a[i] = -1 end for find i such that for any j: a[j] != i create empty result array of size n j = 0; while (i != -1): result[j++] = array[i] i = a[i] end while return result 

If there is no limit to the number of elements that can succeed in each element, then @templatrtypedef's answer gave you the correct one, and your problem is equivalent to finding the Hamiltonian path.

EDIT: The problem is solvable for any well-ordered relationship :
Note that if there can be more than one successor for each element, but the succeed() relation is ordered [no "loops"], you can build a DAG from this problem [each element is a vertex, and for each pair there is an edge such that succeed(a,b) == true ], use the topological order - and return it.
This is also a quadric time, since again - the throat of the bottle finds the edges.

Answer 2

If there are no restrictions on what can be successful (i.e., it should not be transitive, reflexive, symmetrical, etc.), then I think this problem is NP-hard by shortening from NP-hard Hamiltonian path problem . The reduction is actually quite simple: given graph G, create an array of nodes in the graph using the successs relation, so v will succeed in u if there is an edge from u to v in the original graph. Using this setting, searching for a way to arrange array elements (nodes) using the successs relation (linking edges) is equivalent to searching for the Hamiltonian path in the original graph, since each node is visited exactly once. Therefore, you are unlikely to find an efficient algorithm for this if P = NP.

Sorry for the negative result and hope this helps!