Consecutive one's problem

This is a discussion on Consecutive one's problem within the C++ Programming forums, part of the General Programming Boards category; Hey everyone, I am having some difficult trying to calculate the probability of a sequence of consecutive ones being generated ...

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    13

    Consecutive one's problem

    Hey everyone, I am having some difficult trying to calculate the probability of a sequence of consecutive ones being generated in an array when the position is chosen randomly.

    For example: I want to create an array of length K and which entry will be initialized with 0. Then I will select M number of locations that will be picked randomly, once I chose those position I will set it to 1. Now if I try to this problem N number of times, what is the chance I will get a sequence of 1's?

    Like this 1's in an array of 10: 0001111110

    this is what I did to pick a random number for the position:

    Code:
     
    long discrete_uniform (long a, long b)
    {
      if (b > a) {
        double x = uniform ();
        long c = ( a + (long) floor((b-a+1)*x) );
        return c;
      }
      else if (a == b) return a;
      else { printf("ERROR in uniform.discrete_uniform(): a=%2ld b=%2ld\n",a,b);return 0;}
    }
    and then I did a loop to set all the positions to 0. After that I called the discrete_uniform function and set the 1's in the array. But I am having trouble trying to do the code to see if I repeat the experiment N number of times what is the chance that all the 1's will be next to each other.

    I am a beginner, can anyone help me?

  2. #2
    Registered User
    Join Date
    Sep 2009
    Posts
    13
    anyone?

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So you have an array(?) of numbers, some of which are zero and some of which are one. You need to think about how to go through the array and see how many of them are in a row.

  4. #4
    Registered User
    Join Date
    Sep 2009
    Posts
    13
    I thought about it this way:

    Code:
    double consecutiveOnesProbability (int K, int M, int numTrials)
    {
            int randomarray[];
    
            for (int a=0; a<=K; a++){      /* initialize an array with 0's
                    randomarray[a]= 0;
            }
            for (int b=0; b<=M; b++){        /* set 1 in M different positions
                    int i = uniform_discrete(0,9);
                    randomarray[i]=1;
            } 
            for (int e=1; e=k; e++){    /*find the sequence ones
                  int f = randomarray[e];
                  while (f==0)
                           e++;
                  else  if (f==1)
                       saveposition = e;
                       savecount =1;
                       int l=e+1;
                       int h= (e+M)-1;
                          for ( int g=l; g<=h; g++){
                               if (randomarray[g]==1)
                                     savecount=savecount+1;
                               else
                                    printf ("not a sequence"); 
                                    printf ( "Sequence size", savecount);
                           }
                 }
    }

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Are the consecutive ones allowed to involve "wrap around"?
    Where K = 4 and M = 2, that makes the difference between 50% and 67%.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Code:
            int randomarray[];
    I shudder to think that you think this is legal.
    Code:
            for (int a=0; a<=K; a++){      /* initialize an array with 0's
    How many times do you expect this for loop to run?
    Code:
            for (int b=0; b<=M; b++){        /* set 1 in M different positions
    And this one?
    Code:
                    int i = uniform_discrete(0,9);
    Why 0 through 9?
    Code:
            for (int e=1; e=k; e++){    /*find the sequence ones
    How many times do you expect this for loop to run? And how many elements do you intend to miss?

    And after that's done, you need to turn counting into probability.
    Last edited by tabstop; 09-07-2009 at 01:29 PM. Reason: missed a tag

  7. #7
    Registered User
    Join Date
    Sep 2009
    Posts
    13
    No wrap around in this one

  8. #8
    Registered User
    Join Date
    Sep 2009
    Posts
    13
    Quote Originally Posted by tabstop View Post
    Code:
            int randomarray[];
    I shudder to think that you think this is legal.
    Code:
            for (int a=0; a<=K; a++){      /* initialize an array with 0's
    How many times do you expect this for loop to run?
    [/code]
    for (int b=0; b<=M; b++){ /* set 1 in M different positions
    [/code]
    And this one?
    Code:
                    int i = uniform_discrete(0,9);
    Why 0 through 9?
    Code:
            for (int e=1; e=k; e++){    /*find the sequence ones
    How many times do you expect this for loop to run? And how many elements do you intend to miss?

    And after that's done, you need to turn counting into probability.
    The user would entry those values, but you can use K=10 and M=3

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by iMalc View Post
    Are the consecutive ones allowed to involve "wrap around"?
    Where K = 4 and M = 2, that makes the difference between 50% and 67%.
    I assume you mean 37.5% and 50%?
    Quote Originally Posted by Samyx View Post
    The user would entry those values, but you can use K=10 and M=3
    That's nice but completely irrelevant.

  10. #10
    Registered User
    Join Date
    Sep 2009
    Posts
    13
    how did u guys come up with those percentages?

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Samyx View Post
    how did u guys come up with those percentages?
    Counting.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. First Consecutive composites Help
    By ch4 in forum C Programming
    Replies: 10
    Last Post: 11-23-2007, 03:55 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21