How can I find a subarray with some contiguous elements randomly in C?

Question

I have an array with 100 elements. Array elements are a set of ones and zeros. For example:

Array[100] = {0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,....,1}

I need to find all zero windows(gaps) and choose one of them randomly. The size of the gap (needed) is chosen according to a uniform distribution between 1 and 20.

 needed = op_dist_load ("uniform_int", 1, 20);

for example If we assume that the rest of the element are equal to 1 in the Array[100], as you can see, I have 8 zero windows (the size of the window =2). I need to find them.

The find_gap_randomly function selects 2 contiguous zero elements (A subarray with 2 zero elements means that there is a gap in my program). Do you have any suggestions for writing the code of find_gap_randomly(int needed) function in C language without using random library, preferably for OPNET simulator?

static void find_gap_randomly(int needed)
{
    //The macros “FIN” and “FOUT” are used in OPNET functions to enable the OPNET 
    //debugging kernel to print out function information. 
    FIN(find_rr_gap());
    /* ... */
    FOUT;
}

Answer 1

If you are still working on finding the gaps in Array, (a gap defined as the number of sequential zero elements of at least needed length), then a simple, straight-forward way of finding all gaps is to move a "sliding-window" of needed length down the array checking whether all values within the window are zero. If they are all zero, you have found a gap, if not, move to the next index in Array and repeat.

The concept if fairly simple, but a picture may help (or attempted picture)

    +-------+
    |       |  <= window to slide over array
    |       |
    +---+---+---+---+---+---+---+---+...
    | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |   <= array values
    +---+---+---+---+---+---+---+---+...
    0   1   2   3   4   5   6   7   8   <= array indexes
    |       |
    +-------+

Shown above you have the first nine elements of your Array shown, and the corresponding index for each element underneath. Since your needed is 2 you have a window that spans 2-elements that you will move from the beginning to end of Array checking the values within. This can be done simply with two nested loops, the outer loop looping while i = needed; i < num_elements; i++ and then the inner loop iterating from j = i - needed; j < i; j++.

To capture where the gaps within Array are, you use a second array (I called gaps) containing the same number of elements as Array initialized All zero. When you find a region within Array where there a needed number of sequential elements, you simply increment gaps[j]++; to set the value at gaps[j] from 0 to 1. (depending on the scope of j, you may need to increment gaps[i-needed]++; if j has gone out of scope.

When you are done moving your sliding window from beginning to end, gaps will have a value of 1 at each index where the beginning of a gap was located in Array.

A simple function implementing the sliding window could be written like:

/** find_gaps locates each sequence of all zero within 'array' of
 *  at least 'needed' length, the corresponding index within 'gaps'
 *  is incremented to identify the start of each gap, returns the
 *  number of gaps of 'needed' length in 'array'.
 */
int find_gaps (int *gaps, int *arr, int nelem, int needed)
{
    int ngaps = 0;  /* count of gaps found */
    /* add code to validate parameters here */

    memset (gaps, 0, nelem * sizeof *gaps);     /* zero gaps array */
    for (int i = needed; i < nelem; i++) {      /* loop needed to end */
        for (int j = i - needed; j < i; j++) {  /* loop previous needed */
            if (arr[j] != 0)    /* if non-zero value, get next in array */
                goto next;      /* lowly 'goto' works fine here */
        }
        gaps[i-needed]++;   /* increment index in gaps */
        ngaps++;            /* increment no. of gaps found */
      next:;
    }

    return ngaps;   /* return no. of gaps found */
}

(note: the inner loop can be replaced with memcmp to check against a value will all bytes set to zero to locate the gaps)

Go through the operation of find_gaps above, using the diagram as your guide and make sure you understand exactly what is going on. If not, let me know.

Putting it altogether in a short example that takes needed as the 1st argument to the program (or uses 2 by default if no argument is given), you could do something like the following:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

/** find_gaps locates each sequence of all zero within 'array' of
 *  at least 'needed' length, the corresponding index within 'gaps'
 *  is incremented to identify the start of each gap, returns the
 *  number of gaps of 'needed' length in 'array'.
 */
int find_gaps (int *gaps, int *arr, int nelem, int needed)
{
    int ngaps = 0;  /* count of gaps found */
    /* add code to validate parameters here */

    memset (gaps, 0, nelem * sizeof *gaps);     /* zero gaps array */
    for (int i = needed; i < nelem; i++) {      /* loop needed to end */
        for (int j = i - needed; j < i; j++) {  /* loop previous needed */
            if (arr[j] != 0)    /* if non-zero value, get next in array */
                goto next;      /* lowly 'goto' works fine here */
        }
        gaps[i-needed]++;   /* increment index in gaps */
        ngaps++;            /* increment no. of gaps found */
      next:;
    }

    return ngaps;   /* return no. of gaps found */
}

int main (int argc, char **argv) {

    int array[] = { 0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,
                    0,1,1,0,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,1 },
        nelem = sizeof array / sizeof *array,   /* number of elements */
        gaps[nelem],    /* a VLA is fine here C99+, otherwise allocate */
        ngaps = 0,      /* no. of gaps found */
        needed = argc > 1 ? strtol (argv[1], NULL, 0) : 2;  /* (default: 2) */

    if (errno) {    /* validate strtol conversion succeeded */
        perror ("strtol-argv[1]");
        return 1;
    }
    /* find the number of gaps, storing beginning index in 'gaps' array */
    ngaps = find_gaps (gaps, array, nelem, needed);

    printf ("gaps found: %d\n", ngaps);         /* output number of gaps */
    for (int i = 0; ngaps && i < nelem; i++)    /* output index of gaps */
        if (gaps[i])
            printf (" gap at array[%2d]\n", i);

    return 0;
}

(note: you should add checks that needed is less than nelem, but that and any additional validations are left as an exercise for you)

Example Use/Output

$ ./bin/findgaps
gaps found: 11
 gap at array[ 0]
 gap at array[ 9]
 gap at array[10]
 gap at array[11]
 gap at array[12]
 gap at array[18]
 gap at array[19]
 gap at array[25]
 gap at array[26]
 gap at array[32]
 gap at array[37]

Checking for gaps of at least 3 zeros:

$ ./bin/findgaps 3
gaps found: 5
 gap at array[ 9]
 gap at array[10]
 gap at array[11]
 gap at array[18]
 gap at array[25]

There are several ways to approach this problem, but a sliding-window is probably one of the most straight-forward, and the sliding-window has many, many other applications in C, so it is well worth adding to your toolbox. Let me know if you have further questions.