Problem 2189. Order of things - 1

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:t>Let's assume you have a number of calculations to perform, that depend on each other. E.g. 'A' can be calculated, once the outcome of 'B' is known. And 'C' depends on the results of 'A' and 'D'. 'D' depends on 'A'. 'E' depends on all others. Find the right order of the calculations, needed to get all the results. Assume that only one calculation can be done at a time.</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 calculations on each other is expressed in a matrix, where each row and column corresponds to a specific calculation.</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\n A 0 1 0 0 0\n B 0 0 0 0 0\n C 1 0 0 1 0\n D 1 0 0 0 0\n E 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>A '1' 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>In matrix terms, re-order the rows and columns (the same operation applies to both) such that the upper-right triangle, above the diagonal, only contains zeros.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ B A D C E\n B 0 0 0 0 0\n A 1 0 0 0 0\n D 0 1 0 0 0\n C 0 1 1 0 0\n E 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>Return the new row/column order as a numeric row-vector, referring to the rows/columns of the input 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[ [ 2 1 4 3 5 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You may assume that all calculations can be executed, in some order or another.</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>"}]}

Let's assume you have a number of calculations to perform, that depend on each other. E.g. 'A' can be calculated, once the outcome of 'B' is known. And 'C' depends on the results of 'A' and 'D'. 'D' depends on 'A'. 'E' depends on all others. Find the right order of the calculations, needed to get all the results. Assume that only one calculation can be done at a time.The dependencies of the calculations on each other is expressed in a matrix, where each row and column corresponds to a specific calculation.<pre> 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 0 0 0
 E 1 1 1 1 0</pre>A '1' indicates that the calculation on that row depends on the one mentioned at the top of that column.In matrix terms, re-order the rows and columns (the same operation applies to both) such that the upper-right triangle, above the diagonal, only contains zeros.<pre> B A D C E
 B 0 0 0 0 0
 A 1 0 0 0 0
 D 0 1 0 0 0
 C 0 1 1 0 0
 E 1 1 1 1 0</pre>Return the new row/column order as a numeric row-vector, referring to the rows/columns of the input matrix. In this example:<pre> [ 2 1 4 3 5 ]</pre>You may assume that all calculations can be executed, in some order or another.

Let's assume you have a number of calculations to perform, that depend on each other. E.g. 'A' can be calculated, once the outcome of 'B' is known. And 'C' depends on the results of 'A' and 'D'. 'D' depends on 'A'. 'E' depends on all others. Find the right order of the calculations, needed to get all the results. Assume that only one calculation can be done at a time.

The dependencies of the calculations on each other is expressed in a matrix, where each row and column corresponds to a specific calculation.

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  0  0  0
 E  1  1  1  1  0

A '1' indicates that the calculation on that row depends on the one mentioned at the top of that column.

In matrix terms, re-order the rows and columns (the same operation applies to both) such that the upper-right triangle, above the diagonal, only contains zeros.

B  A  D  C  E
 B  0  0  0  0  0
 A  1  0  0  0  0
 D  0  1  0  0  0
 C  0  1  1  0  0
 E  1  1  1  1  0

Return the new row/column order as a numeric row-vector, referring to the rows/columns of the input matrix. In this example:

[ 2 1 4 3 5 ]

You may assume that all calculations can be executed, in some order or another.

Solve

Solution Stats

65 Solutions
16 Solvers

Last Solution submitted on May 21, 2021

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Jean-Marie Sainthillier on 2 Mar 2014

Maybe a clue or a link to understand this family of problem.

J-G van der Toorn on 3 Mar 2014

The background is that I encountered this problem when analysing experimental data. Different acquisition modules were used simultaneously. Timing data from one signal was used to calculate a delay from another. The offset from again another was to be subtracted from a couple of others. An area under a resulting curve was to be devided by another area, taking into account the timing signal. In other words, there were multiple interconnected processing steps, with cross-dependencies.
This inspired me to write this Cody-task.

Problem Recent Solvers16

Problem Tags

algorithm matrix order

Community Treasure Hunt

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

Start Hunting!