6
$\begingroup$

I have an issue for which I am looking for an algorithm (if it exists)

What I have: An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$.

Example: $[ A(x,y), B(x,y), C(x,y), D(x,y), E(x,y) ]$

What I want: A result list consisting of elements of the original list, such as $[ A(x,y), C(x,y), E(x,y) ]$, for which the following properties are true:

  • No reordering of elements, they are in the same order as the original list
  • The result has the maximum number of elements, i.e. the longest 'path' possible
  • For each pair of consecutive items $(A(x,y), B(x,y))$ in the result, $A.x \lt B.y$. In other words, an item's $x$ must be less than the next item's $y$.

Complexity: The list in the case I have is about 35 items long, so an algorithm which is $O(n!)$ might not work.

Does such an algorithm exist?

$\endgroup$
  • $\begingroup$ Perhaps try a backtracking algorithm? That should be O(2^n) which you could always change to a dynamic program of (hopefully) O(n^2). The only problem I forsee is that the recursion has no idea if you choose to include A not C, whether or not A.x < E.y. $\endgroup$ – ardent Jun 19 '13 at 19:41
  • $\begingroup$ See cs.stackexchange.com/questions/4985/… and cs.stackexchange.com/a/6548/5323 $\endgroup$ – András Salamon Jun 19 '13 at 21:28
  • $\begingroup$ @AndrásSalamon Yes, that looks very much related $\endgroup$ – Dutchy Jun 20 '13 at 9:25
  • $\begingroup$ @AndrásSalamon $A.x < B.y$ isn't transitive, I think this makes a big difference. $\endgroup$ – Gilles 'SO- stop being evil' Jun 20 '13 at 9:49
5
$\begingroup$

It's easier to change notation. Suppose the array is $A$, with the $i$-th element denoted $A[i]$ for $i=1,2,\dots,n$, and that element $i$ has attributes $A[i].x$ and $A[i].y$. Associate a directed graph $G$ with the array as follows. The vertices of $G$ are the indices $1\dots n$ of the array. Vertex $i$ is connected to vertex $j\ $ if both conditions $i<j$ and $A[i].x < A[j].y\ $ hold.

You are then asking for a longest directed path in $G$.

Note that $G$ is actually acyclic, since the arcs form a subset of the usual order on the set $\{1,\dots,n\}$. Any standard linear algorithm can then be used to compute the longest path, such as a topological sort.

$\endgroup$
-2
$\begingroup$

So, your comparison is based on numerical properties x and y? If this is the case, then do some kind of sorting algorithm first, and adjust the order after sorting so that your condition of no reordering holds (that is delete those elements that are not at the correct location).

$\endgroup$
  • 3
    $\begingroup$ I'm afraid you misunderstood. The properties must hold afterwards, I can't sort on them. Note also that they are 2 properties, if item1.x < item2.y, item2.x might be a totally different value. $\endgroup$ – Dutchy Jun 19 '13 at 17:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.