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.

Solve

Solution Stats

62 Solutions
7 Solvers

Last Solution submitted on Oct 29, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

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.

Problem Recent Solvers7

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 45503. Place wastewater treatment processes in the correct order

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author19

Problem Tags

Community Treasure Hunt

Problem 45503. Place wastewater treatment processes in the correct order

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author19

Problem Tags

Community Treasure Hunt

Players