CODEWITHSUNDEEP
algorithm
T .
T .

Reputation: 4944

Ordering a set of items with constraints

I'm looking for an algorithm that allows me to order a set so that a set of conditions are met. The conditions can only be "must appear before" or "must appear after". For example:

Two valid solutions would be "ACDBE" and "EACDB". I only care to find a single valid solution.

I have no idea how to implement this. Maybe I just don't know the correct name for this, and I would be able to find information if I did.

What would be an algorithm that allows me to find a solution? Or what is this kind of algorithm called (what should I Google)?

Upvotes: 0

Views: 238

Answers (2)

M.Soyturk
M.Soyturk

Reputation: 370

Topological sort by using graph is probably the best way to do it, yet you can follow another approach by using position based list(like PositionalList ADT in Java) and sorting it while traversing by using "after,before" method.

Upvotes: 0

gchelfi
gchelfi

Reputation: 89

It looks like you are looking for a topological sort.

The idea is that you can encode your dependencies in a directed graph: your set elements are nodes, and your conditions are edges. There is an edge between A and B if and only if "A must appear before B".

A topological sort is guaranteed to find a valid solution for your problem if it exists, and there are well-known algorithms with a linear time complexity on the size of the graph.

Upvotes: 4

Related Questions