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
Solved

C - 2 dimensional array loop

Posted on 2006-11-08
8
273 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
  • 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
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
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

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Not needed 13 119
Arduino EDI - Programming Language - Voice Recorder 4 94
ejb example issues 3 26
WordPress: Debugging from my Windows 10 Desktop 6 35
Whether you've completed a degree in computer sciences or you're a self-taught programmer, writing your first lines of code in the real world is always a challenge. Here are some of the most common pitfalls for new programmers.
"Disruption" is the most feared word for C-level executives these days. They agonize over their industry being disturbed by another player - most likely by startups.
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…

860 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