Solved

C - 2 dimensional array loop

Posted on 2006-11-08
8
265 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
 
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
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
A short article about problems I had with the new location API and permissions in Marshmallow
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
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…

747 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now