Problem 2192. Order of things - 4

Created by J-G van der Toorn

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:rPr><w:b/></w:rPr><w:t>This is the last assignment in the</w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t> </w:t></w:r><w:r><w:rPr><w:b/><w:i/></w:rPr><w:t>Order of Things</w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>-series. If that past incompleteness kept you from solving it, you may start now.</w:t></w:r><w:r><w:t> Open that bottle of wine, and spend an entertaining evening coding.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This problem is closely related to</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.nl/matlabcentral/cody/problems/2189-order-of-things-1\"><w:r><w:t>Problem 2189, Order of things - 1</w:t></w:r></w:hyperlink><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.nl/matlabcentral/cody/problems/2190-order-of-things-2\"><w:r><w:t>Problem 2190, Order of things - 2</w:t></w:r></w:hyperlink><w:r><w:t>, and</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.nl/matlabcentral/cody/problems/2191-order-of-things-3\"><w:r><w:t>Problem 2191, Order of things - 3</w:t></w:r></w:hyperlink><w:r><w:t>. For the details, see the description for those problems. Basically, we have to find the order in which to execute tasks of which the results and prerequisites depend on each other.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>However, this is the most complex case, as * Calculations are preferably grouped, but may, due to their dependencies, not all be clustered. So groups of events may be split over different clusters. The number of clusters per group should be kept to a minimum.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The same complications as in problem 3 may apply: * It may (still) be impossible to find a solution, since dependencies may be cyclic. But this is now no longer due to the grouping of tasks, as you may, if necessary, break the rule of grouping. In any case, return an empty vector if no order is found. * There are still multiple orders possible, return them as multiple rows of the output vector. * The tasks within a group should of course be specified in the right order, when interdependent.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The dependencies of the tasks on each other is expressed in a matrix, where each row corresponds to the execution of a task, and each column to the dependency.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ A B C D E\nA 0 0 0 0 0\nB 0 0 1 0 0\nC 1 0 0 0 0\nD 0 0 1 0 0\nE 1 0 0 0 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>1</w:t></w:r><w:r><w:t> on row</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>C</w:t></w:r><w:r><w:t>, column</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>B</w:t></w:r><w:r><w:t>, indicates that task</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>C</w:t></w:r><w:r><w:t> depends on task</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>B</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>The grouping of tasks is expressed as an input vector with groups assigned an integer value &gt; 0, for every task, e.g.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ [ 1 1 2 2 3 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Return the new row/column order as a numeric row-vector, referring to the rows/columns of the input matrix. If multiple orders exist, return them all as rows of a matrix. In this example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ [ \n 1 3 4 2 5\n 1 3 4 5 2\n 1 5 3 4 2\n ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If no order fulfilling the dependencies exists, return an empty vector.</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>"}]}

This is the last assignment in the Order of Things-series. If that past incompleteness kept you from solving it, you may start now. Open that bottle of wine, and spend an entertaining evening coding.This problem is closely related to <a href = "http://www.mathworks.nl/matlabcentral/cody/problems/2189-order-of-things-1">Problem 2189, Order of things - 1</a>, <a href = "http://www.mathworks.nl/matlabcentral/cody/problems/2190-order-of-things-2">Problem 2190, Order of things - 2</a>, and <a href = "http://www.mathworks.nl/matlabcentral/cody/problems/2191-order-of-things-3">Problem 2191, Order of things - 3</a>. For the details, see the description for those problems. Basically, we have to find the order in which to execute tasks of which the results and prerequisites depend on each other.However, this is the most complex case, as 
* Calculations are preferably grouped, but may, due to their dependencies, not all be clustered. So groups of events may be split over different clusters. The number of clusters per group should be kept to a minimum.The same complications as in problem 3 may apply:
* It may (still) be impossible to find a solution, since dependencies may be cyclic. But this is now no longer due to the grouping of tasks, as you may, if necessary, break the rule of grouping. In any case, return an empty vector if no order is found.
* There are still multiple orders possible, return them as multiple rows of the output vector.
* The tasks within a group should of course be specified in the right order, when interdependent.The dependencies of the tasks on each other is expressed in a matrix, where each row corresponds to the execution of a task, and each column to the dependency.<pre> A B C D E
A 0 0 0 0 0
B 0 0 1 0 0
C 1 0 0 0 0
D 0 0 1 0 0
E 1 0 0 0 0</pre>The <tt>1</tt> on row <tt>C</tt>, column <tt>B</tt>, indicates that task <tt>C</tt> depends on task <tt>B</tt>.The grouping of tasks is expressed as an input vector with groups assigned an integer value &gt; 0, for every task, e.g.<pre> [ 1 1 2 2 3 ] </pre>Return the new row/column order as a numeric row-vector, referring to the rows/columns of the input matrix. If multiple orders exist, return them all as rows of a matrix. In this example:<pre> [ 
 1 3 4 2 5
 1 3 4 5 2
 1 5 3 4 2
 ]</pre>If no order fulfilling the dependencies exists, return an empty vector.

Solve

Solution Stats

19 Solutions
2 Solvers

Last Solution submitted on Jun 11, 2016

Last 200 Solutions

Problem Recent Solvers2

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 2192. Order of things - 4

Solution Stats

Last 200 Solutions

Problem Recent Solvers2

Suggested Problems

More from this Author31

Problem Tags

Community Treasure Hunt

Problem 2192. Order of things - 4

Solution Stats

Last 200 Solutions

Problem Recent Solvers2

Suggested Problems

More from this Author31

Problem Tags

Community Treasure Hunt

Players