Problem 45503. Place wastewater treatment processes in the correct order
There are many technologies for treating wastewater. For example, grit chambers are used to remove heavy solids, filtration is used to remove smaller solids, chemical oxidation disinfects the water from bacteria, and so on. By performing these steps one after the other, it is possible to recycle sewage water back to nature.
However, the steps must be performed in the correct order, i.e. some technologies must be performed before others. In this problem, we will label these technologies as 1, 2, ... N. You are then given a [ K x 2] matrix called P, which is a list of constraints to be read as follows:
"Technology P( i, 1) must be performed before P( i, 2)," for all rows i.
Your task is to list all N technologies from left to right in the order that they should be performed, that is, without violating any constraint. If there are multiple possible orderings, choose the one in which the technologies with the smaller labels come earlier. Your output will be essential for designing the sequence of steps in a wastewater treatment plant.
Consider the following example:
N = 4; P = [1 2; 3 4]; Possible orderings: [1 2 3 4], [1 3 2 4], [1 3 4 2], [3 1 2 4], [3 1 4 2], [3 4 1 2]. Desired ordering: [1 2 3 4]
Another example:
N = 4; P = [2 1; 2 4]; Possible orderings: [2 1 3 4], [2 1 4 3], [2 3 1 4], [2 3 4 1], [2 4 1 3], [2 4 3 1], [3 2 1 4], [3 2 4 1]. Desired ordering: [2 1 3 4]
Write a function that takes N and P, then output the desired ordering.
You are ensured that 1 <= N <= 100 and 1 <= K <= 100. All elements of P are within [1, N]. Furthermore, none of the constraints will be conflicting.
Solution Stats
Problem Comments
-
3 Comments
This whole set of Chem problems are all inspiring, I do enjoy solving every single one of them. please keep it up, hope we can see more.
I agree with bainhome. They are very well done. Thanks KEP!
I agree with both bainhome and ChrisR; this problem set has been a pleasure all around. Well-written, interesting, and teaching you something new, both about graph theory and about MATLAB's facilities for solving graph-theoretic problems. Thank you!
Solution Comments
Show commentsProblem Recent Solvers15
Suggested Problems
-
Given an unsigned integer x, find the largest y by rearranging the bits in x
1806 Solvers
-
Fermat's Last Theorem - Fermat's conjecture
100 Solvers
-
190 Solvers
-
139 Solvers
-
Deriving a function using the difference quotient
68 Solvers
More from this Author19
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!