Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 287
  • Last Modified:

C - 2 dimensional array loop

Sorry about the 20 pts, for some reason my question points aren't increasing for answering questions.  I will get some points and raise this one high for anyone that answers it.

Here is some quick background info:
In C, I have created a 5x5 transition matrix that contains conditional probabilities of state changes (Markov Chain).  Each row is a state. Each column represents the probability of moving to that next state. Each row will add up to 1.0  For example, using the following matrix, starting from state S0, the transition probability of moving to state S2 then state S4 is (0.4 * 0.1)

       S0   S1 S2  S3  S4
S0{ 0.3 0.1 0.4 0.1 0.1 }
S1{ 0.6 0.1 0.0 0.2 0.1 }
S2{ 0.9 0.0 0.1 0.0 0.1 }
S3{ 0.2 0.3 0.2 0.1 0.2 }
S4{ 0.6 0.1 0.1 0.1 0.1 }


My problem is that I need to figure out a loop (iterative or recursive) to compute the transition probabilities of each possible path of 20 steps in the matrix.  This will result in 5^20 possible paths (5 states and 20 steps).  To give a nice visual, here is an example of the states I need to calculate:

00000000000000000000
00000000000000000001
00000000000000000002
00000000000000000003
00000000000000000004
00000000000000000010
00000000000000000011
00000000000000000012
...
44444444444444444444

Does anyone have any idea how to write a loop to do this, bc I havn't had any luck in days?  If needed, I can post the source code I have or give further explanations.

Thanks!!!
0
deadite
Asked:
deadite
  • 4
  • 3
1 Solution
 
InteractiveMindCommented:
Try something like this:



double S [][] = { { 0.3, 0.1, 0.4, 0.1, 0.1, },
                         { 0.6, 0.1, 0.0, 0.2, 0.1, },
                         { 0.9, 0.0, 0.1, 0.0, 0.1, },
                         { 0.2, 0.3, 0.2, 0.1, 0.2, },
                         { 0.6, 0.1, 0.1, 0.1, 0.1 } };


/* the probability of moving from state A to state B */
double P(int A, int B)
{ return S[A][B]; }


int path [20];

/* iterate to produce all possible combinations; then process each on */
int state(int depth)
{
    int i;
    for(i=0; i<sizeof(S[0])/sizeof(S[0][0]); i++)
    {
        path[depth]=i;
        if(depth==20-1)
        {
            process();
        }else
        {
            state(++depth);
        }
    }
}

/* process each path */
void process()
{
    double P=1;
    int i;
    for(i=0; i<20-1; i++)
    {
        P *= P(path[i], path[i+1]);
    }
   
    // the probability of going through the path in the 'path' array is 'P'.
    // output it here in whatever format you want..
}



then to start this whole process, make the following call:

state(0);



(Keep in mind that it's almost 1 AM here, and I got up before 6 AM yesterday morning.. so be sure to test that before accepting!! :))
0
 
deaditeAuthor Commented:
Thanks for the reply, however... I am unable to get this to compile correctly in order to test it...
0
 
Arthur_WoodCommented:
"my question points aren't increasing for answering questions"  The points you earn for answering questions are NOT the same as the points you use to ASK questions.  They are not inter-changeable.

AW
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
InteractiveMindCommented:
you will have needed to made some alterations to my above code...
(add a main() function, added some includes; prototypes if necessary; etc..)
show me your full code that you're trying to compile.. (if it's any different to the above?)
0
 
InteractiveMindCommented:
try something like this


#include <stdio.h>


const double S [][5] = { { 0.3, 0.1, 0.4, 0.1, 0.1, },
                         { 0.6, 0.1, 0.0, 0.2, 0.1, },
                         { 0.9, 0.0, 0.1, 0.0, 0.1, },
                         { 0.2, 0.3, 0.2, 0.1, 0.2, },
                         { 0.6, 0.1, 0.1, 0.1, 0.1 } };


/* the probability of moving from state A to state B */
double P(int A, int B)
{ return S[A][B]; }


int path [20];

/* process each path */
void process()
{
    double P_=1;
    int i;
    for(i=0; i<20-1; i++)
    {
        P_ *= P(path[i], path[i+1]);
    }
   
    printf("%s","P(");
   
    for(i=0; i<20-1; i++)
        printf("%i",path[i]);
   
    printf(") = %e\n",P_);
}

/* iterate to produce all possible combinations; then process each on */
int state(int depth)
{
    int i;
    for(i=0; i<5; i++)
    {
        path[depth]=i;
        if(depth==20-1)
        {
            double P_=1;
           
            int j;
            for(j=0; j<20-1; j++)
            {
                P_ *= P(path[j], path[j+1]);
            }
   
            printf("%s","P(");
   
            for(j=0; j<20-1; j++)
                printf("%i",path[j]);
   
            printf(") = %e\n",P_);
        }else
        {
            state(depth+1);
        }
    }
}


int main()
{
    state(0);
    return 0;
}
0
 
InteractiveMindCommented:
you don't actually need the process method anymore. i've made it a little more compact:


#include <stdio.h>

const double S [][5] = { { 0.3, 0.1, 0.4, 0.1, 0.1, },
                                    { 0.6, 0.1, 0.0, 0.2, 0.1, },
                                    { 0.9, 0.0, 0.1, 0.0, 0.1, },
                                    { 0.2, 0.3, 0.2, 0.1, 0.2, },
                                    { 0.6, 0.1, 0.1, 0.1, 0.1  } };

int path [20];


/* the probability of moving from state A to state B */
double P(int A, int B)
{ return S[A][B]; }

/* iterate to produce all possible combinations; then process each on */
int state(int depth)
{
    int i;
    for(i=0; i<5; i++)
    {
        path[depth]=i;
        if(depth==20-1)
        {
            double P_=1;
            int j;
            for(j=0; j<20-1; j++)
            {
                P_ *= P(path[j], path[j+1]);
            }
   
            printf("%s","P(");
            for(j=0; j<20-1; j++)
                printf("%i",path[j]);
            printf(") = %e\n",P_);
        }else
        {
            state(depth+1);
        }
    }
}

/* execute */
int main()
{
    state(0);
    return 0;
}
0
 
deaditeAuthor Commented:
That code looks great....  I do have a question about combining it with mine.  I was randomly generating the markov table using random #'s as floats, then averaging them to make them add up to 1.0.  Do you think I'd be better changing this code to use doubles or try to modify your code to use floats?  Here is my code (yes it is sloppy):

int main() {



/* Set Random Seed from System Time for rand() */
srand(time(NULL));



/* Create Markov array */
float arrMarkov[MAXROW+1][MAXCOL+1];



/* Fill Markov array with Random numbers */
int row;
int col;
float rnum;
printf("Original Table with Random Numbers\n");
for (row = 0; row <= MAXROW; row++) {
    printf("Row %i [", row);
    for (col = 0; col <= MAXCOL; col++) {
        rnum = (float)(rand() % 11) / 10;
        arrMarkov[row][col] = rnum;
        printf("%f ", rnum);
    }
    printf("]\n");
}



/* Make rows add up to one */
printf("\n");
float sum = 0;
float temp;
int r;
for (row = 0; row <= MAXROW; row++) {
    /* Sum Columns */
    for (col = 0; col <= MAXCOL; col++) {
        sum = sum + arrMarkov[row][col];
    }
    /* Divide Column by Column Sum */
    for (col = 0; col <= MAXCOL; col++) {
        temp =(arrMarkov[row][col] / sum);
        /* Change float to int with 2 sig digits to remove extra numbers - Nasty
Hack! */
        r =  temp * 1000;
        printf("%f / %f = %f * 1000 = %i", arrMarkov[row][col], sum, temp, r);
        /* Round to Hundredths Place - always adds up to 1.0 */
        if ((r % 10) >= 5) {
            r = (r * .1) + 1;
        } else {
            r = (r * .1);
        }
        printf(" = %i", r);
        /* Round to Tenth Place - Doesn't always add to 1.0! */
        if ((r % 10) >= 5) {
            r = (r * .1) + 1;
        } else {
            r = (r * .1);
        }  
        printf(" = %i", r);
        /* Change rounded int back to float - Nasty Hack! */
        arrMarkov[row][col] = r * .1;        
        printf(" = %f\n", arrMarkov[row][col]);
    }
    sum = 0; /* Reset sum to 0 for next row */
}
0
 
deaditeAuthor Commented:
Forgot to post the defines I used:
#define MAXROW 4
#define MAXCOL 4

Which I need to change these to 5 and remove the +1's from the code yet.
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

  • 4
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now