Combination generator written in C : works for big n but for small n when n=0 or n=k crashes saying "segmentation fault"

Question

Let's say I have a box and there is a bunch of balls in that box. I can label each ball with a character while making sure no two balls get the same character as labels. I get a string this way. Let's say I had 5 balls in the box and I label them alphabetically, then the string I will get is abcde. Now let's say I want to pick 3 balls randomly from the box, which can be done in 10 different ways and I will get 10 different strings of length 3, arranged alphabetically these will be -

abc abd abe acd ace ade bcd bce bde cde

I want to write a computer programme that will be doing the same thing. It will -

1. Ask for a string from the user.
2. Calculate the length of the string n.
3. Ask for a number k less than or equal to the length of the string.
4. Calculate binomial coefficient nCK.
5. Declare a nCK X k+1 matrix comb.
6. Declare an array of nCK pointers ptr.
7. Set the value of all of the elements of ptr to be equal to the corresponding addresses of the rows of comb.
8. Compute all possible combinations by calling the function gen_comb () and store the values in comb.
9. Print the combinations by calling the function prnt_comb and repeat.

I wrote the following -

#include <stdio.h>

void length (char * string, int * n)
{
    *n = 0;
    for (int i = 0; string[i] != '\0'; i++)
    {
        *n = *n + 1;
    }
}

void bin_cof (int * n, int * k, int * nCk)
{
    int _k; *nCk = 1;
    if (*k > *n - *k)
    {
        _k = *n - *k;
        
    } else {
        _k = *k;
    }
    for (int i = 0; i < _k; i++)
    {
        *nCk = *nCk * (*n - i) / (1 + i);
    }
}

void first_n_last (char * string, char ** current, char ** last, int * n, int * k)
{
    for (int i = 0; i < *k; i++)
    {
        current[i] = string + i;
    }
    current[*k] = string + *n;
    for (int i = 0; i < *k; i++)
    {
        last[i] = string + i + *n - *k;
    }
    last[*k] = string + *n;
}

void prnt_comb (char ** ptr, int * nCk, int * k)
{
    printf ("\nHere is the set of %d possible combination of length %d :\n\n{%s", *nCk, *k, ptr[0]);
    for (int i = 1; i < *nCk; i++)
    {
        printf (", %s", ptr[i]);
    }
    printf ("}\n\n\n");
}

void successor (char * string, char ** current, char ** last, int k)
{
    int con;
    for (int i = k-1; i >= 0; i--)
    {
        if (current[i] != last[i])
        {
            con = i; break;
        }
    }
    char * i = string;
    for (;i != current[con]; i++) {}
    int poi = (int) (i-string);
    for (; con < k; con++)
    {
        current[con] = string+1+poi; poi++;
    }
}

void gen_comb (char * string, int *n, int * k, int * nCk, char ** ptr)
{
    char * current[*k+1], * last[*k+1];
    first_n_last (string, current, last, n, k);
    for (int j = 0; j < *nCk; j++)
    {
        for (int i = 0; i < *k+1; i++) {ptr[j][i] = *(current[i]);}
        successor (string, current, last, *k);
    }
}

int main ()
{
    for (;;)
    {
        printf ("Give me a string : ");
        char string [100];
        if (scanf("%s", string) == 0)
        {
            printf ("Error!!");
            break;
        }
    
        int n;
        length (string, &n);
        printf ("Give me a number less than or equal to %d : ", n);
        int k;
        if (scanf("%d", &k) == 0)
        {
            printf ("Error!!");
            break;
        }
    
        int nCk;
        bin_cof (&n, &k, &nCk);
        char comb[nCk][k+1], * ptr[nCk];
        for (int i = 0; i < nCk; i++)
        {
            ptr[i] = comb[i];
        }
        
        gen_comb (string, &n, &k, &nCk, ptr);
        prnt_comb (ptr, &nCk, &k);
    }
    return 0;
}

It works for big ns, but for small ns (less than 7 or 8 let's say) when k becomes 0 or becomes equal to n it crashes saying "Segmentation fault, core dumped." And it does so completely randomly, sometimes when n=4 && k=4 it will crash, other times when n=2 && k=0 it will crash. Randomly. But, for big numbers, n>8 let's say, it works fine. Where is this error originating from and how can it be eliminated? I am running the programme here.

Answer 1

Your coding style is unusual and difficult to read. It is beneficial to use a more classic style that will make it easier for other programmers to read your code and for yourself to get more proficient by reading other people's code.

Here are some dos and don'ts:

• pass variables by value
• use return to return a function result instead of passing a destination variable by reference.
• write a single statement per line
• attach the * pointer indicator to the variable or function name
• use separate declarations for pointers
• enable more compiler warnings and fix the problems detected by the compiler
• always compare the return value of scanf() with the expected number of conversions to detect invalid, but also missing input.
• use index variables instead of pointers if possible

Indeed your function successor has a problem that is easily caught by the compiler: con is never initialized if k is 0. The loop for (;i != current[con]; i++) {} will then invoke undefined behavior because con can have any value including one that is well beyond the end of the array, causing the CPU to trigger a Segmentation fault, ie: accessing a segment of memory that does not belong to the process.

Here is a simplified version:

#include <stdio.h>

int length(const char *string) {
    int n = 0;
    for(int i = 0; string[i] != '\0'; i++) {
        n = n + 1;
    }
    return n;
}

int bin_coef(int n, int k) {
    int nCk = 1;
    if (k > n - k)  {
        k = n - k;
    }
    for (int i = 0; i < k; i++) {
        nCk = nCk * (n - i) / (i + 1);
    }
    return nCk;
}

void prnt_comb(char **ptr, int nCk, int k) {
    printf("\nHere is the set of %d possible combination of length %d :\n\n{ %s", nCk, k, ptr[0]);
    for (int i = 1; i < nCk; i++) {
        printf(", %s", ptr[i]);
    }
    printf(" }\n\n");
}

void successor(int *current, int k, int n) {
    for (int i = k - 1; i >= 0; i--) {
        if (current[i] != i + n - k) {
            int j = current[i];
            for (; i < k; i++) {
                current[i] = j += 1;
            }
            return;
        }
    }
}

void gen_comb(const char *string, int n, int k, int nCk, char **ptr) {
    int current[k];
    for (int i = 0; i < k; i++) {
        current[i] = i;
    }
    for (int j = 0; j < nCk; j++) {
        for (int i = 0; i < k; i++) {
            ptr[j][i] = string[current[i]];
        }
        ptr[j][k] = '\0';  // set null terminator
        successor(current, k, n);
    }
}

int main(void) {
    for (;;) {
        printf("Give me a string: ");
        char string[100];
        if (scanf("%99s", string) != 1) {
            printf("Error!\n");
            break;
        }

        int n = length(string);
        printf("Give me a number less than or equal to %d: ", n);
        int k;
        if (scanf("%d", &k) != 1) {
            printf("Error!\n");
            break;
        }
        if (k < 0 || k > n) {
            printf("Invalid number %d\n", k);
            break;
        }

        int nCk = bin_coef(n, k);
        char comb[nCk][k + 1];
        char *ptr[nCk];
        for (int i = 0; i < nCk; i++) {
            ptr[i] = comb[i];
        }

        gen_comb(string, n, k, nCk, ptr);
        prnt_comb(ptr, nCk, k);
    }
    return 0;
}

Answer 2

There are a couple of problems here.

1. The SIGSEGV (Seg fault) is not random at all it happens always. When k = n regardless of the size of input. It's just that with small number it's more probable that you hit a bad address, try compiling with -g3 and -fsanitize=address to check for segfaults explicitly.

2. asan will reveal that the segfault is in successor(), at line 53. When you are using mod to index inside current, if the every character of last is equal to every respective character of current mod remains uninitialized and you will access current with a random garbage address, causing the Segfault