cancel
Showing results for 
Search instead for 
Did you mean: 
cancel
Showing results for 
Search instead for 
Did you mean: 

Matrix path

Highlighted
Regular Member

Matrix path

I am trying to work out how to calculate all the paths from each cell in column zero to the end column.

This is part of project to calculate the remaining strength in a material.  The matrix represents a grid on the material.  Each cell in the matrix contains a measured parameter at a location on the grid.

I need to calculate the sum of all the paths available from each of the cells in column zero.  The path can progress one cell up or one cell down or one cell across.  It can never go backwards.

 

In the attached file is a grid of 5 x 7, with fictitious data.  In reality the grids are more likely to be 20 x 40.

 

I can see how to do it manually but I cannot see how to do it within Mathcad.

 

Any direction or guidance would be appreciated.

 

The system will not allow me to attach a file. "The contents of the attachment doesn't match its file type", which is nonsense because it is an mcdx file.

 

 

 

Thank you

Tags (2)
15 REPLIES 15

Re: Matrix path

Hi,

 

please explain how do you calculate the sum of all the paths manually.


Martin Hanák

Re: Matrix path

Good Morning Martin,

Thank you for replying to my post.

 

I mapped out the first few rows manually.  For example, if we assume an origin of 1 and the rows labelled A to D and the columns 1 to 7 and we start at cell A1.

 

A1 can go to A2 or B1.  If it goes to A2 then it can go to A3 or B2.  If it goes to A3 then it can go to A4 or B3 etc.

 

A2 can go to A1 A3 and B2 etc.

 

From that you can build up all of the paths possible from A1.  Then you have to move to A2 and repeat the performance.

 

Then you can sum up the value total for each path and perform various calculations on them.

 

I hope that is clear.

 

Kind Regards

Re: Matrix path

Hi,

 

1.]

If I understand you well, the path can start in any matrix cell. This means in 1,1 an also in 3,7 (for example).

 

2.]

If I understand you well, the path ends in 7th column. This means step from 2,7 to 3,7 is forbidden.

 

3.]

Are you able to create program solving your problem in any programming language ? I mean Basic, C, Pascal, ...


Martin Hanák

Re: Matrix path

There are still some questions.

1) Is the following correct: We never go to the left and we never go back (up or down) from where we came. That way endless paths are excluded


2) Where does a path end. You wrote that it spans from the first column to the last one.

 

2a) Are we allowed to go up or down when we reach the rightmost column or

 

2b) do we have to stop immediately when we reach the first time a cell in the last column?
In other words: Is C1-C2-C3-B3-B4-B5-B6-B7-C7 a valid path or not?


3) What should the result be? You wrote "I need to calculate the sum of all the paths available from each of the cells in column zero." What means "sum of all the paths"?

3a) Are you just interested in the number of paths possible from each of the cells in the first column. The result being a 5-element vector representing the number of paths for each of the 5 start cells.
This is probably not what you are looking for, as the values in the cells would be irrelevant and the result would be the same for any cell in the first column -> r^(c-1) if you have a r x c matrix.

3b) Do you intend to add all numbers for all paths possible from a start cell? The result being a 5-element vector and each element is the total sum of of all cell values for all paths possible from each of the 5 start cells.

3c) Similar as 3b), but this time the sum of values is listed separately for each path. That way for each start cell we would have a list of results. The result could be either represented by a nested 5-element vector and this time the elements would be vectors again, representing the cell sums of each of the 15625 paths possible from a start cell. Or you could represent the result in a 5 * 15625 matrix.
You will of course loose any information as to which path which value belongs to.
For a 20 x 40 matrix the result would be a matrix with 20 rows and 5.498*10^50 columns!! Guess this is also not what you are looking for, right?

Whatever the result should be - I think that the easiest approach would be a function which is called recursively. There is no easy, ready-made function available you could use out of the box. You will have to use some programming.

I can't read your file with my version of Prime so I can't see if you just provided a 5 x 7 matrix or if you already have tried some approach. You may consider attaching a screenshot or a pdf-print of your file in the latter case.

Re: Matrix path

OK, I gave it a try.

 

I am assuming that from my reply above that 1) , 2b) and 3b) apply.

 

Its just a quick hack and it seems that it will be almost endless until a calculation for a 20 x 40 matrix finishes.

A recursive appoach often is the easiest one, but seldom the most efficient or most reliable one.

So while my program sure can be improved  I guess for a substantial better performance you would have to chose a different approach.

 

I attach the file in Mathcad 15 format and provide a screenshot. You may either convert the file or retype the small programm if you want to give it a try.

 

Pic.png

 

If you look at the formula for the number of possible paths I sent in my previous post, its no surprise that adding rows rather moderately increase the calc time but adding columns let the time explode. After all the rows are at the base, but the columns in the exponent (n = r^(c-1))

Pic3.png

Based on those numbers a 20 x 40 matrix would take about 3 * 10^39  years. Even if your machine is 100 times faster than mine ..... you sure won't want to wait.

Guess a better approach than the brute force recursive one may be to find a formula to determine how often a cell is part of a path.

 

EDIT: Just realized that my program seems to return wrong results!!

Have to recheck if I have some more time.

In the meantime waitung for your answers to all the questions above.

Re: Matrix path

Dear Werner,

 

Thank you.  I will copy the program into Prime and run it.  

 

Kind Regards

Re: Matrix path


@klax wrote:

Dear Werner,

 

Thank you.  I will copy the program into Prime and run it.  

 

Kind Regards


No! Don't do that! Read my comments about calculation time and look at my EDIT. The program returns wrong values (I missed a few cells in recursion).

Rather answer the questions above to make sure, what you really  need!

 

Re: Matrix path

Here is the corrected routine.

Still the same issue with calculation time, of course.

Still waiting for your answers.

PIC.png

 

Re: Matrix path

Dear Werner,

 

Thanl you for your continued interest.

 

Here are the responses (I have coloured themblue to make them easier to pick out):

1) Is the following correct: We never go to the left and we never go back (up or down) from where we came. That way endless paths are excluded  Correct.  Note that diagonal moves are not permitted in any direction


2) Where does a path end. You wrote that it spans from the first column to the last one.  Path ends at the last column

 

2a) Are we allowed to go up or down when we reach the rightmost column or.  No.

 

2b) do we have to stop immediately when we reach the first time a cell in the last column?
In other words: Is C1-C2-C3-B3-B4-B5-B6-B7-C7 a valid path or not? Not valid.  You can only go one cell at a time, so from C1 you can only go to B1 or D1

3) What should the result be? You wrote "I need to calculate the sum of all the paths available from each of the cells in column zero." What means "sum of all the paths"?  Each cell has the data relating to the material condition at that point.  The sum of the material loss at each location on the path is averaged and then applied to a formula which gives the remaining strength.  This calculation is applied for all paths.

3a) Are you just interested in the number of paths possible from each of the cells in the first column. The result being a 5-element vector representing the number of paths for each of the 5 start cells.
This is probably not what you are looking for, as the values in the cells would be irrelevant and the result would be the same for any cell in the first column -> r^(c-1) if you have a r x c matrix.  It is not just the number of paths but the actual route of each of the paths that is important.

3b) Do you intend to add all numbers for all paths possible from a start cell? The result being a 5-element vector and each element is the total sum of of all cell values for all paths possible from each of the 5 start cells. Yes

3c) Similar as 3b), but this time the sum of values is listed separately for each path. That way for each start cell we would have a list of results. The result could be either represented by a nested 5-element vector and this time the elements would be vectors again, representing the cell sums of each of the 15625 paths possible from a start cell. Or you could represent the result in a 5 * 15625 matrix.
You will of course loose any information as to which path which value belongs to.
For a 20 x 40 matrix the result would be a matrix with 20 rows and 5.498*10^50 columns!! Guess this is also not what you are looking for, right? Right!

Whatever the result should be - I think that the easiest approach would be a function which is called recursively. There is no easy, ready-made function available you could use out of the box. You will have to use some programming.

I can't read your file with my version of Prime so I can't see if you just provided a 5 x 7 matrix or if you already have tried some approach. You may consider attaching a screenshot or a pdf-print of your file in the latter case.  I just provided a 5 x 7 matrix with some random values in.

 

Kind Regards