Basic help in programming with matrix

[aktarjahan2003]

Hi
Need some help about symetric matrix calculation. Need some generic formula to calculate in particular order.

-1 51 54 25 77
51 -1 44 70 96
54 44 -1 87 94
25 70 87 -1 88
77 96 94 88 -1

I want to add several items to make an array of sum in this order.
Example,
sum = 01 +12 + 23 + 34+ 45
(start with element row 0 column 1, last column number is index for next element)

some more example:
sum = 01 +13 + 34 + 45+ 52
sum = 01 +14 + 45 + 52+ 23
sum = 01 +15 + 52 + 23+ 34

sum = 02 +23 + 34 + 45+ 51
sum = 02 +24 + 45 + 51+ 13 and so on.

Each sum should take maximum number (maximum row or column, an item column is row for next item and each column is taken only one times)
as number of items in the matrix. If row and column is same we don't add it or if the cell value is -1.

How can I generelize these?

Br
Aktar

[hamsterman]

Your question is hard to understand.

So you have a matrix, say M and you want to find the sum M_ab + M_bc + M_cd + ... for some indices a=0, b=1, c, d, ...
How are these indices determined. Are they chosen to maximize the sum? How long is this sum?

And what do you mean by "generalize"? Do you just want an algorithm?

[aktarjahan2003]

Hi hamsterman !

Thanks for reply. I knew it is hard. Generilize mean I want to have algorithm that can be used in code. Or if some body has code if I can share it.

say we have total row = column = f

sum = M_ab + M_bc + M_cd + M_de + M_ef

sum = M_bc + M_cd + M_de + M_ef + M_fa

sum = M_bd + M_df + M_fa + M_ab + M_bc

If there are factorial (f-1) types of sum. I need the sum in an array.
When I find the sum, once a column index has been used, it can't be used if you see the pattern.

If I use row index a then column index can be any index between 0 to f
row index can be between 0 to f without repeating the column index.

[hamsterman]

So you want to find all such sums?

It seems easy enough. pseudocode:

columns = {2, 3, 4, 5}

for each i < 4! {
   choices = i'th permutation of columns
   row = 0
   col = 1
   sum = matrix[row][col]
   for each j < 4 {
      row = col     
      col = choices[i]
      sum[i] += matrix[row][col] if it is not -1
   }
}

You can find permutations using http://cplusplus.com/reference/algorithm/next_permutation/

[aktarjahan2003]

Hi hamsterman !

Great ! Thanks lot.

Oh Yes it is easy with algorithm. It díd not come to my mind to use it.
Next permutation is giving me what I need,

Thanks for pointing that. I am going to put it in my application in Qt, if it is supported there then I am done if not do you know can I get the algorithm code for next permutation?

[hamsterman]

next_permutation is in the standard library which is available everywhere (don't forget to #include <algorithm> )

If you're interested in how it works, see http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

[aktarjahan2003]

Hi,
Is there any C++ code that I can use for the sort and next_permutation methods. I tested my theory in Windows with these and worked great but if I tried to use it in Qt I get errors

error: 'sort' was not declared in this scope
error: 'next_permutation' was not declared in this scope

Can I get the implementation of these so I can include it in my project?

Thanks

Aktar

[hamsterman]

Did you add #include <algorithm> and append std:: to the names or write something with using?

[aktarjahan2003]

Yes, I did, sorry I forgot to mention in the post

edit: sorry I gave wrong information, there was other mistake now it works nicely.

Thanks for great help

Aktar Jahan

hemelix.com