Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Problem 2189. Order of things - 1

Created by J-G van der Toorn

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.

Tags

Problem Group

Solution Statistics

6 correct solutions 11 incorrect solutions
Last solution submitted on Mar 24, 2014

Problem Comments