Problem 2190. Order of things - 2

Created byJ-G van der Toorn

Like (2)

Solve Later

{“关系”:[{“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>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>. For the details, see the description for that problem. 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=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>However, this time it may be impossible to find a solution, since dependencies may be cyclic. In that case, return an empty vector.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Furthermore, if there are multiple orders possible, return them as multiple rows of the output vector.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Again, the dependencies of the tasks on each other is expressed in a matrix, where each row and column corresponds to a specific task. Each row expresses on which result that task depends. A</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> indicates that the calculation on that row depends on the one mentioned at the top of that column.</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. Of an empty array when no solution is possible. Or a matrix of rows containing the orders, where each row is a different solution, in case multiple solutions exist.</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 1 0 0 0\nB 0 0 0 0 0\nC 1 0 0 1 0\nD 1 0 1 0 0\nE 1 1 1 1 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The above problem can not be solved, since</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</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>D</w:t></w:r><w:r><w:t>, which in its place depends on</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>. The returned value would be</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>[]</w:t></w:r><w:r><w:t> .</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 1 0 0 0\nB 0 0 0 0 0\nC 1 0 0 0 0\nD 1 0 0 0 0\nE 1 1 1 1 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The returned matrix should be</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ [\n 2 1 3 4 5 \n 2 1 4 3 5\n ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Good luck!</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 problem is closely related to <http://www.mathworks.nl/matlabcentral/cody/problems/2189-order-of-things-1 Problem 2189, Order of things - 1>. For the details, see the description for that problem. Basically, we have to find the order in which to execute tasks of which the results and prerequisites depend on each other. * However, this time it may be impossible to find a solution, since dependencies may be cyclic. In that case, return an empty vector. * Furthermore, if there are multiple orders possible, return them as multiple rows of the output vector. Again, the dependencies of the tasks on each other is expressed in a matrix, where each row and column corresponds to a specific task. Each row expresses on which result that task depends. A |1| indicates that the calculation on that row depends on the one mentioned at the top of that column. Return the new row/column order as a numeric row-vector, referring to the rows/columns of the input matrix. Of an empty array when no solution is possible. Or a matrix of rows containing the orders, where each row is a different solution, in case multiple solutions exist. A B C D E A 0 1 0 0 0 B 0 0 0 0 0 C 1 0 0 1 0 D 1 0 1 0 0 E 1 1 1 1 0 The above problem can not be solved, since |C| depends on |D|, which in its place depends on |C|. The returned value would be |[]| . A B C D E A 0 1 0 0 0 B 0 0 0 0 0 C 1 0 0 0 0 D 1 0 0 0 0 E 1 1 1 1 0 The returned matrix should be [ 2 1 3 4 5 2 1 4 3 5 ] Good luck!

Solve

Solution Stats

15 Solutions
10 Solvers

LastSolutionsubmitted on Nov 06, 2021

Last 200 Solutions

Problem Comments

解决方案Comments

Solution 406514

1 Comment

1 Comment

J-G van der Toornon 20 Feb 2014

Since Cody, I dislike for-loops, but your solution is way simpler than my own algorithm. Mission accomplished...
尽管如此，我希望有一条非循环的代码。让我们在第3阶段中看看。

Problem Recent Solvers10

来自作者的更多31

Robust alignment of coordinate system
2 Solvers
Number of problems
104 Solvers
Order of things - 4
2 Solvers
Insert structure in a parameter-cell array.
15 Solvers
A SUBSREF variant that accepts the 'end'-operator.
5 Solvers

Problem Tags

Community Treasure Hunt

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

开始狩猎！