Solved

C - 2 dimensional array loop

Posted on 2006-11-08
8
278 Views
Last Modified: 2013-11-13
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
Comment
Question by:deadite
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
8 Comments
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 17903043
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
 
LVL 8

Author Comment

by:deadite
ID: 17903559
Thanks for the reply, however... I am unable to get this to compile correctly in order to test it...
0
 
LVL 44

Expert Comment

by:Arthur_Wood
ID: 17904081
"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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 25

Expert Comment

by:InteractiveMind
ID: 17904714
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
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 17905461
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
 
LVL 25

Accepted Solution

by:
InteractiveMind earned 20 total points
ID: 17905475
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
 
LVL 8

Author Comment

by:deadite
ID: 17906432
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
 
LVL 8

Author Comment

by:deadite
ID: 17906452
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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

This is about my first experience with programming Arduino.
Today, the web development industry is booming, and many people consider it to be their vocation. The question you may be asking yourself is – how do I become a web developer?
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

734 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question