Problem 45503. Place wastewater treatment processes in the correct order

Created by Karl Ezra Pilario

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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, ...</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t>. You are then given a [</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>K</w:t></w:r><w:r><w:t> x 2] matrix called</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>, which is a list of constraints to be read as follows:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>\"Technology</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>, 1) must be performed</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>before</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>, 2),\" for all rows</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your task is to list all</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> 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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Consider the following example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[N = 4; P = [1 2;\n 3 4];\nPossible orderings: [1 2 3 4], [1 3 2 4], [1 3 4 2],\n [3 1 2 4], [3 1 4 2], [3 4 1 2].\nDesired ordering: [1 2 3 4]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Another example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[N = 4; P = [2 1;\n 2 4];\nPossible orderings: [2 1 3 4], [2 1 4 3], [2 3 1 4], [2 3 4 1],\n [2 4 1 3], [2 4 3 1], [3 2 1 4], [3 2 4 1].\nDesired ordering: [2 1 3 4]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write a function that takes</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t>, then output the desired ordering.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are ensured that 1 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> &lt;= 100 and 1 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>K</w:t></w:r><w:r><w:t> &lt;= 100. All elements of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t> are within [1,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t>]. Furthermore, none of the constraints will be conflicting.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

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:<pre class="language-matlab">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]
</pre>Another example:<pre class="language-matlab">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]
</pre>Write a function that takes N and P, then output the desired ordering.You are ensured that 1 &lt;= N &lt;= 100 and 1 &lt;= K &lt;= 100. All elements of P are within [1, N]. Furthermore, none of the constraints will be conflicting.

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.

Solve

Solution Stats

78 Solutions
13 Solvers

Last Solution submitted on Jan 11, 2023

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

bainhome on 18 May 2020

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.

ChrisR on 31 May 2022

I agree with bainhome. They are very well done. Thanks KEP!

Christian Schröder on 18 Oct 2022

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!

Problem Recent Solvers13

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!