loop building question

This is a discussion on loop building question within the C Programming forums, part of the General Programming Boards category; Hello, I am trying to build a loop that makes a matrix diagnolly dominant (I'm not sure if thats the ...

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    84

    loop building question

    Hello, I am trying to build a loop that makes a matrix diagnolly dominant (I'm not sure if thats the right term... I mean where the values on the diagnol are from greatest to least... like this

    like if I was given this:
    Code:
    2 3 7 8
    9 2 3 4
    5 9 0 6
    3 8 4 3
    I would get this:

    Code:
    9 2 3 4
    3 8 4 3
    2 3 7 8
    5 9 0 6
    with 9,8,7,6 making this diagnolly dominant.

    I'm not looking for code but am wondering if anyone has any ideas on the simplest way to go about this...

    I'm having a hard time thinking on how to approach this, I'm thinking

    1) compare the entire first column
    2) take the line with the largest first column value and switch
    it with first line
    3) lock the first line then compare colum 2 in the following 3 lines
    put largest value for column 2 line as second line
    4) lock the 2nd line check the third column last two lines
    if the 3rd line has the larger value switch those as well....


    at this point I'm thinking my algorithm is running into trouble...

    any suggestions would be greatly appreciated.

    Thank You

  2. #2
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    Basically you set to swap your largest value in each column with an increasing x,y index.

    Something like this perhaps.
    Code:
    const int xMax = 4;
    const int yMax = 4;
    int Array[xMax][yMax], diag, column, row;
        
    for (diag = 0, column = 0; diag < xMax && diag < yMax 
         && column < yMax; diag++, column++) {
        for (row = 0; row < xMax; row++) {
            if (Array[row][column] > Array[diag][diag])
              swap(Array[row][column], Array[diag][diag]); // Function must be defined
        }
    }
    That handles putting the highest values in the diagonal. Your second part of ordering that diagonal the way you do is slightly more difficult because it assumes that the succeeding row has at least one value less than the highest value in the last row.

    Now I could set the if statement to be handle like this:
    Code:
    if (Array[row][column] > Array[diag][diag] && diag == 0)
            swap(Array[row][column], Array[diag][diag]); // Function must be defined
    else if (Array[row][column] > Array[diag][diag] && Array[row][column] < Array[diag-1][diag-1])
            swap(Array[row][column], Array[diag][diag]); // Function must be defined
    This will order it properly and when implemented in a simple program I wrote, I see that it does work correctly.

    Output:
    Code:
     8 6 6 1
     5 4 3 6
     5 1 2 3
     4 2 4 1
    
     8 4 6 1
     5 6 2 6
     5 1 4 1
     4 2 3 3
    ...but these were random numbers between 1 and 9, where there is a good chance of not running into the situation of succeeding row not having at least one value less than the highest value in the last row. If I were to say do random numbers between 1-50, I would run into the error more often.
    Last edited by SlyMaelstrom; 11-30-2005 at 02:06 PM.
    Sent from my iPadŽ

  3. #3
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    ...and after a few runs of my program, here is a clear example of why this can be problematic.

    Code:
    6 2 1 7
    2 2 6 6
    4 2 1 6
    7 5 1 6
    
    7 2 1 7
    2 5 6 6
    4 2 1 6
    6 2 1 6
    What would you wish to have done in this situation?
    Sent from my iPadŽ

  4. #4
    Registered User
    Join Date
    Sep 2005
    Posts
    84
    well, what I'm trying to do is something different than what yours does.. i'm trying to take in a matrix and just switch around the rows, for instance for the matrix you made:

    Code:
    6 2 1 7
    2 2 6 6
    4 2 1 6
    7 5 1 6
    Would turn to:
    Code:
    7 5 1 6
    4 2 1 6
    6 2 1 7
    2 2 6 6
    Just moving the rows in order to make the diagnol line (In the above case 7,2,1,6)
    In a decending order from greates to least...

    Like
    Code:
    2 3 7 8
    9 2 3 4
    5 9 0 6
    3 8 4 3
    would turn into:

    Code:
    9 2 3 4
    3 8 4 3
    2 3 7 8
    5 9 0 6
    with the 9,8,7,6 dignol being the ultimate goal here.

  5. #5
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    No, that's not what my code does. It orders the row putting the greatest value (that is less than the previous diagonal value) into the diagonal. Look at my output again.

    Code:
     8 6 6 1
     5 4 3 6
     5 1 2 3
     4 2 4 1
    
     8 4 6 1
     5 6 2 6
     5 1 4 1
     4 2 3 3
    The two things you'll have to add for checks is: One, you have to make sure there isn't a higher value in the diagonal initally before the swap. Two, you have to make sure each column has at least one value lower than the preceding column.
    Last edited by SlyMaelstrom; 11-30-2005 at 10:27 PM.
    Sent from my iPadŽ

  6. #6
    Registered User
    Join Date
    Sep 2005
    Posts
    84
    no, no... what I mean is that your code is not moving the rows.... my code needs to just move rows to provide the diagnol

    none of these rows
    Code:
     8 6 6 1
     5 4 3 6
     5 1 2 3
     4 2 4 1
    exist in your output.... I need to just move entire rows... for example 8 6 6 1 would have to exist in the output so would 5 4 3 6 and so on, I have to move rows in order to get thh dignol

    so the matrix above is already diagnolly dominant and does not need to be adjusted, it would come out of the code looking the same since there are no rows you can move to make it diganolly dominant

    Code:
    8
      4
        2
          1
    is diganolly dominant already

  7. #7
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    Ahhhh... Ok, no problem then. Just look into sorting algorithms. Then do swaps whole rows.
    Sent from my iPadŽ

  8. #8
    Registered User
    Join Date
    Sep 2005
    Posts
    84
    I've been looking on google for some kind of sorting algorithm that would help with this, but I can't find any... I think this might be called a diagnolly dominant matrix... but I can't find any algrithms on it.... I'm suppose to do it by only using if and do loops....

    I'm doing this:
    1) compare the entire first column
    2) take the line with the largest first column value and switch
    it with first line
    3) lock the first line then compare colum 2 in the following 3 lines
    put largest value for column 2 line as second line
    4) lock the 2nd line check the third column last two lines
    if the 3rd line has the larger value switch those as well....

    but when I get to the last coumn the previous three rows I have locked where I'm not checking agains them anymore... and I get stuck at this point in my thinking

    anyone know a different way I might apporach this?

  9. #9
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    You can do this with a bubble sort if you wanted to.

    Compare [0][0] with [1][1]. If [1][1] is bigger, swap the entire rows. Then continue on... it's not much more difficult than any other sort.
    Sent from my iPadŽ

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. For loop question
    By JuzMe in forum C++ Programming
    Replies: 11
    Last Post: 04-20-2009, 08:39 AM
  2. Loop question
    By kwood965 in forum C Programming
    Replies: 6
    Last Post: 10-29-2008, 11:12 PM
  3. simple for loop function question
    By felicityxiv in forum C Programming
    Replies: 7
    Last Post: 05-06-2006, 11:43 PM
  4. Please don't laugh...SIMPLE loop question!
    By the_lumin8or in forum C++ Programming
    Replies: 5
    Last Post: 03-31-2006, 12:08 PM
  5. while loop question
    By rayrayj52 in forum C++ Programming
    Replies: 2
    Last Post: 10-19-2004, 05:13 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21