Need algorithm for Sequence calculation

Question

I am trying to find the solution for a problem where i have something like

1. A > B
2. B > C
3. B > D
4. C > D

And I should get the answer as A > B > C > D.

Conditions for this problem

1. The output will involve all the elements.
2. The problem will not have any bogus inputs. for example, (A>B) (C>D) is a bogus input, since we cannot determine the output.
3. The inputs can be of any size but never bogus and there will always be a solution to the problem.

I need to find a solution for this optimally using Java Collections. Any tips/hints are welcome.

Thanks in advance!

Answer 1

It's called a Topological Sort. http://en.wikipedia.org/wiki/Topological_sorting

Given that, you should be able to complete your homework on your own.

Answer 2

I'm betting you recently covered graphs in this class...
How do you think a graph could be applied here ?
Can you think of a structure which one would build on the basis of the problem inputs (A>B>, A>D, C>A etc.)? Maybe some kind of directed graph...

Once the problem is expressed in such a graph, the solution would involve navigating this graph...

Answer 3

You start putting them in a List. The list will be sorted, so for the nth pair (a, b), you look up a, using a binary search. If it exists already skip, if not you insert in at proper point. Since a > b, you do that again with b in the remaining part of the List. Hope this help.

Answer 4

You can do this with a Map of the inputs and a recursive method that adds it's answer to a returned List (or just prints each node as it descends the tree.) If you are returning the answer then pre-pending to the returned list will prevent the answer from being reversed D->C->B->A when complete (or you can just .reverse() the list at the end.) Don't forget to test for a break condition when recursing. (hint: key not found)