Need help completing the code of program

[miss_Lolitta]

Hi all,,
I am hoping that you will help me. I have trouble how I can complete the code of program that allows the user to input a number of integers such as N, and then stores them in an integer matrix where:

1- The dimension of matrix = NXN.
2-Entries of matrix can take any number from 0-2.
3- Arrangement of entries of first row is the same arrangement of entries of first column.
4-The diagonal of matrix =o.
5- Total of every row =4,Also Total of every column.

Then, the program displays all probabilities as table.


I tried to write this code but I can't complete it. just I want to find all probabilities for the rest of rows.I hope you don't have mind to help me to complete that.(please,,l ook at attachement)


Your help would greatly be appreciated

Thanks in advance..

Respectfully,,
Miss_Lolitta

[shinelakshmanan]

can all the elements of a particular row except diagonal element have the same value......

[Banfa]

You question is not clear. For some reason you start talking about probabilities half way through with no previous reference.

The code appeared to assign 2 to every entry on the first row when I ran it.

You haven't actually stated what it is that the code should do, just some of the conditions.

[miss_Lolitta]

The code in attachment is not complete,becaus e I don't know how I can satisfied the rest of conditions?

more detail:
Idea of program:
1- this program compute how many ways can draw curves cross points" points is a number which input by user also it is the dimension of matrix".

2- From point to itself has no intersection, that is the diagonal of matrix =o ,,but from any point to another one can found more than one intersection (0-1-2).

*************** *************** *************** *************** ****

How the program do?:

For example:

I- If user enter N=3 we have a following matrix

0 2 2
2 0 2
2 2 0

Which satisfying all conditions:
1- The dimension of matrix = 3×3
2-Entries of matrix can take any number from 0-2.
3- Arrangement of entries of first row is the same arrangement of entries of first column.
4-The diagonal of matrix =o.
5- Total of every row =4, Also Total of every column.


II- If user enter N=4 we have following matrices whose dimension is 4×4
*************** *************** *********
0 0 2 2
0 0 2 2
2 2 0 0
2 2 0 0
*************** *************** **********
0 2 0 2
2 0 2 0
0 2 0 2
2 0 2 0
*************** *************** **********
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0
*************** *************** **********
0 2 2 0
2 0 0 2
2 0 0 2
0 2 2 0
*************** *************** **********
0 2 1 1
2 0 1 1
1 1 0 2
1 1 2 0
*************** *************** **********
0 1 1 2
1 0 2 1
1 2 0 1
2 1 1 0
*************** *************** **********

thanks for all..

regards,.
Lolitta

[Banfa]

Ah I see so the program has to produce all matrices that satisfy the conditions, OK.

(just for information where you have used the word probabilities either combinations or solutions would have been better which is why I was a little confused).

Right we are getting somewhere so

You have fully describe the problem you are trying to solve
You have indicated that you have a problem, however you have not really described the problem except to post some code and state that it doesn't work. Really you should describe your problem too.


However I have look at your code and I will make some comments

FindPossibleOpt ion

You have a problem in the way this function is defined/called. The first parameter is Number *, and you only ever call it with mat[i] where i=0, i.e. you only ever access the first line of your matrix.

You have come up against a common problem in C, handing round a dynamically create array of more than 1 dimension (in this case 2). In C I would solve this by using a array of only 1 dimension and just accessing like 2 dimensions.

However you have an alternitive, because you are using C++ you could create a matrix class and encapsulate the memory allocation and deallocation andhave a function to access the individual matrix cells. Then your functions could pass round either a pointer or reference to the class.

At the very least you need to pass Number ** to FindPossibleOpt ion or iterate through all the rows in order to solve this problem.

The reset option to this function seems of little use, it sets the values of some static variables that are not used elsewhere in the code.


The internal workings of InitMat and ClearMat are a little odd since they work in BOOL where everything else works in Number.


Can you post the logic you think you are solving with the function FindPossibleOpt ion and the functions it calls.

[miss_Lolitta]

As you know the decimal system and binary system are numeral systems. They depend on a number we call the base number. For example the decimal system base number is 10. That means there are 10 numbers 0~9 and the base number needs 2 digits and will look like 1 beside a 0 that means 10. When the base number is 3 the system contain 3 digits 0~2 and the base number also will look like (10)3. In that case the system is called trinary system.

Hereby, I think it would be nice to cal that you want to fill the matrix using trinary numbers to satisfy other conditions. The question is why we may need that? The answer is to make all the possible options look like a sequence.

Example:
fill a vector of 4 values with the first is zero and the other three ranges from 0~2.
Sol: I will solve as it is decimal then transfer in trinary.
A0 A1 A2 A3 Trinary number Sum decimal
Always
0 0 0 (0)3 0
0 0 1 (1)3 1
0 0 2 (2)3 2
0 1 0 (3)3 1
0 1 1 (4)3 2
0 1 2 (5)3 3
0 2 0 (6)3 2
0 2 1 (7)3 3
0 2 2 (8)3 4
1 0 0 (9)3 1
1 0 1 (10)3 2
1 0 2 (11)3 3
1 1 0 (12)3 2
1 1 1 (13)3 3
1 1 2 (14)3 4
1 2 0 (15)3 3
1 2 1 (16)3 4
1 2 2 (17)3 5
2 0 0 (18)3 2
2 0 1 (19)3 3
2 0 2 (20)3 4
2 1 0 (21)3 3
2 1 1 (22)3 4
2 1 2 (23)3 5
2 2 0 (24)3 4
2 2 1 (25)3 5
2 2 2 (26)3 6

Note that 26 is number of digits in this case 3 power by the base number also 3.

Total options is (digits)base =27 (from 0 to 26(

So what we did now? We just could generate all possibilities of that three numbers using one loop. In C++ terminology we need to transferee from decimal to trinary and vise versa. But the binary should be in the matrix form to get the index of the digits.

Here are two functions made for that purpose

// Transfer from Decimal to trinary
// no: decimal number
// row the array (started from 0 as usual with C and C++)
// size is over all size 
//  row StartInd is the starting point of filling the array 
// EndInd is the end location 
 
void DectoMat3(int no,Number*  row, int size, int StartInd, int EndInd)
{
    for(int k=EndInd; k>=StartInd; k--){
        row[k] = no%BASE_NO;
        no /= BASE_NO;
    }
} 
 
int Mat3toDec(Number*  row, int size, int StartInd, int EndInd)
{
    int fac = 1, power, res=0;
    for(int k=EndInd; k>=StartInd; k--){
        power = EndInd-k;
        for(int j=1; j<=power; j++){
            fac *= BASE_NO;
        }
        res += fac * row[k];
    }
    return(res);
} 
 
 
 

if we talk about case N=4,we get some solutions for first row which satisfy sum =4 from elements 0,1,2 as:

2 2 0 0
2 0 2 0
2 1 1 0
1 2 1 0
1 1 2 0
0 2 2 0

this is a first step,find all solutions for first row.let us write this operation at function FindPossibleOpt ion

int main(void)
{
    Number **mat=NULL;
    int size=0;
 
    if(!(mat=CreateMat(&size))){
        return(1);
    }
//-->////Program start here
    int i=0; 
    FindPossibleOption(mat[i], size, SUM, 1,size-1, TRUE);
    PrintMat(mat, size);
    while(FindPossibleOption(mat[i], size, SUM, 1, size-1, FALSE) ){
        PrintMat(mat, size);
    }
//-->// End of Program
 
    ClearMat(mat, size);
    getch();
    return(0);
}
 
 

[Banfa]

Wow! I think that has to be about the most compete answer I have ever received on these forums :D

OK Here are my suggestions (these may just be the first step to a solution not the actual solution).

FindPossibleOpt ion
Actually I am very impressed with the maths and logic, however you need to modify this function, currently it finds the first row for all solutions, it needs to be capable of finding all rows for all solutions. Here are some of the things that are blocking that

The variable j (this is extremely poorly named, for a variable as important as this is to the working of your code you should give it a meaningful name). This variable is a major stubling block to solving the problem because the is only 1 of it. However I little thought indicates that you will need 1 for each row (because for any given solution for row 1 there may be more than 1 solution for the rest of the rows) so the data that controls the logic (j and count) need to be held for each row currently being processed and since each row is dependent on all previous rows (because the matrix is reflected on it's diagonal) that means that when solving the penultimate row you will be in the middle of solving all rows.

So the mechanism for storing j needs to external to FindPossibleOpt ion and needs to be a vector of N-1 values for an NxN array. (N-1 because you never have to solve the last row).

Also insolving a row you solve a column so FindPossibleOpt ion needs access to the whole matrix so it can fill in the columns as well as the rows as it solves them.

Finally EndInd will always be size-1 and since you pass in size you do not need to pass in EndInd.

So you need to rewrite FindPossibleOpt ion so that it doesn't contain the definition and initialisation of j and count (NOTE bits does not need to be static), it can handle rows other than row 1 and it does fill in the column solved as well as the row solved. It might have a prototype that looks like

BOOL FindPossibleOpt ion(Number **matrix, Number &decimal, int size, int rowSum, int StartInd);


Then in main your loop is not complex enough, everytime you find a solution to row 1 you have to continue and find a solution to all the other rows something like

int main(void)
{
    Number **mat=NULL;
    int size=0;
 
    if(!(mat=CreateMat(&size))){
        return(1);
    }
 
    Number *vec = new Number[size];
 
    if (vec == NULL) {
        exit(EXIT_FAILURE);
    }
 
    // Set all row values to 0
    memset((void *)vec, 0, sizeof(*vec) * size);
 
//-->////Program start here
    int row = 0;
 
    for(;;) {
        BOOL rowOK = FindPossibleOption(mat, vec[row], size, SUM, row+1);
 
        if ( rowOK ) {
            if ( row == size-2 ) {
                // penultimate row OK 
                // therefore matrix complete so print it
                PrintMat(mat, size);
 
                // Now look for next solution on previous row
                row--;
                vec[row]++;
            }
            else
            {
                // This row has a solution look for solution on next row
                // Have to start search from beginning again
                row++;
                vec[row] = 0;
            }
        }
        else {
            if (row == 0) {
                // No more solutions for row 1 so end of calculation
                break;
            }
            else {
                // No more solutions for current row
                // look for next solution on previous row
                row--;
                vec[row]++;
            }
        }
    }
//-->// End of Program
 
    ClearMat(mat, size);
    delete[] vec;
    getch();
    return(0);
}
 

Make sure that you understand how that loop I wrote works, also depending on how you re-write FindPossibleOpt ion it may need tweaking.

[Banfa]

Opps the are 2 errors in my loop in the section dealing with a found solution

            if ( row == size-2 ) {
                // penultimate row OK 
                // therefore matrix complete so print it
                PrintMat(mat, size);
 
                // Now look for next solution on previous row
                row--;
                vec[row]++;
            }
 

The first is that there may be further solutions on the current row, we don't want to start looking at the previous row, this is easy to fix

            if ( row == size-2 ) {
                // penultimate row OK 
                // therefore matrix complete so print it
                PrintMat(mat, size);
 
                // Now look for next solution on previous row
                vec[row]++;
            }
 

The second is that although we do not need to calculate the last row we do need to check that it meets all the requirements (adds up to 4) before we print the solution, I will leave you to write this code.

[miss_Lolitta]

thanks for all responding..
I'll try to rewrite code again..

thank u so much

[D_C]

Wow this is an interesting problem. I was looking at a recursive way, and I think I found how it could be done with a balance of brute force and elegance. If you solved it, though, keep it the way you have it. Also, I haven't actually ran the code, so if there are any errors, you need to understand the code to fix it, which isn't such a bad thing :D.

Matrix dimension N, Max Increment B (identically 2), total value T (identically 4).

• int array of size (N*(N-1))/2, for unique matrix entries
• two int arrays of size N, for row and column sums

Actually each array entry needs at most ceiling(log base 2 (T+B)). This would be three bits for your scenario, B=2 and T =4.

Using some nested loops and recursion, you can make a pretty algorithm that would look quite ugly if followed on paper. Don't forget, unique_entries, row_sum and col_sum data should be static, so they may be accessed from the middle of the code. It would be wasteful to pass it every time.

int col(int c) // trim symmetric half and diagonal entries
{              // 0=>(0,1), N-1=>(0,N), and (N*(N-1))/2=>(N,N)
  int dim = N-1;
  int add = 0;
  while(c > dim)
  {
    c -= dim;
    dim--;
    add++;
  }
  return (c+add);
}
 
 int row(int c); // same as col(int) except return (1+add);
 
// PROBLEM SOLVING ROUTINE
 solve(int index) 
{
  if(index == LENGTH) // LENGTH = (N*(N-1))/2
    return;
 
  for(j = 0; j <= B; j++)
  {
    unique_entries[index] = j; // unique_entries
    row_sum[row(index)] += j;
    col_sum[col(index)] += j;
 
    // Because of matrix symmetry
    row_sum[col(index)] += j;
    col_sum[row(index)] += j;
 
    check to see if all entries of row_sum and col_sum = T
    if so, print matrix, then continue without returning.
 
    if j != 0, see if any of the four modified is now greater than T.
    if j != B, see if we are too far away from T, i.e. 000X or 001X.
    // X is a don't care, because any value it takes, it won't help.
 
    if either condition is violated, return;
    else recursively call solve(index+1);
 
    // Almost forgot
    row_sum[row(index)] -= j;
    col_sum[col(index)] -= j;
    row_sum[col(index)] -= j;
    col_sum[row(index)] -= j;
  }
}