Permutation code in C

Question

I am pretty new to competitive programming. It took me almost 3 hours to make this, initially I started with 4 for loops and then to make it scalable for sizes bigger than 4, I decided to turn this into a recursion which is when it took most of my time, even though I am proud of it, I am still worried that it took me an hour to actually come up with the solution and I have a feeling that it is neither efficient nor good, (you could say I am basically doing combination rather than permutation), I would like a code review please and how would you make this more efficient?

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

int counter = 0;

int factorial(int n){
    if(n==1) return 1;
    else return n*factorial(n-1);
}

int index_present_check(int* n_arr, int n, int depth){
    for(int i = 0 ; i < depth ; i++) if(n_arr[i]==n) return 1;
    return 0; 
}

int present_in_array_check(char** store_arr,char* arr_to_print,int counter){
    for(int i = 0; i < counter; i++) if(strcmp(store_arr[i],arr_to_print)==0) return 1;
    return 0;
}

void permutation(int depth,int length,char* src_arr, char* arr_to_print,int*     n_arr,char** store_arr){
    for(int i = 0 ; i < length ; i ++){
        if(depth ==1){
            arr_to_print[0] = src_arr[i];
            n_arr[0] = i;
            permutation(depth+1,length,src_arr,arr_to_print,n_arr,store_arr);
        }
        else{
            if(!index_present_check(n_arr,i,depth)){
                arr_to_print[depth-1] = src_arr[i];
                n_arr[depth-1] = i;
                permutation(depth+1,length,src_arr,arr_to_print,n_arr,store_arr);
                n_arr[depth-1] = -1;
            }
        }
    }
    if(depth==length){
        if(!present_in_array_check(store_arr,arr_to_print,counter)){
            printf("%s ",arr_to_print);
            strcpy(store_arr[counter],arr_to_print);
            counter++;
            if(counter%factorial(length-1)==0){
                printf("\n");
            }
        }
    }
}



int main()
{
    char* src_arr = "ABCDE";
    int length = 4;
    int depth = 1;

    int iteration_length = factorial(length);

    char* arr_to_print = malloc(length*sizeof(char));
    int* n_arr = malloc(length*sizeof(int));
    char** store_arr = (char**)malloc(sizeof(char*)*iteration_length);
    for(int i = 0 ; i<iteration_length;i++) store_arr[i] = malloc(sizeof(char)*length);

    permutation(depth,length,src_arr,arr_to_print,n_arr,store_arr);

    return 0;
}

I posted this in reddit too, but it was a bit off timing and didn't get much code review, however it was helpful nonetheless.

Toby Speight · Accepted Answer · 2020-03-02 16:57:49Z

There are only two versions of the main function:
```
/* 1 */
int main(int argc, char *argv[]) { ... }

/* 2 */
int main(void) { ... }
```
Note the void keyword in the second version. In C, if the function has no parameters it should be declared as
```
 <type> f(void)
```
Please, take a look at this SO answer for details.

Do not write one-line code:

for(int i = 0; i < counter; i++) if(strcmp(store_arr[i],arr_to_print)==0) return 1;

I'd rewrite it this way:

for (int i = 0; i < count; i++)
    if (strcmp(store_arr[i], arr_to_print) == 0)
        return 1;

Do not use int as type for array indexing. It is not guaranteed that int can hold any possible index value of an array object. The only type that can hold any index of an array object is size_t. See this SO answer for details.
I'd replace
```
printf("\n");
```
with
```
putchar('\n');
```
Do not cast the result of malloc call. Really, you have to do it in C++, but not in C. See this SO question for details.
Do not repeat yourself. Consider this line:
```
int* n_arr = malloc(length * sizeof(int));
```
You declare n_arr as a pointer to int. It would be better to rewrite this line in this way:
```
int *n_arr = malloc(length * sizeof *n_arr);
```
In this case you don't have to change the expression of the sizeof operator if you change n_arr type. It is very common C idiom.
Do not computer factorial using recursion. It is really slow. Usually, you can just create the factorial table and hardcode it:
```
static const unsigned long long factorial_table[] = {
    1,
    2,
    6,
    24,
    120,
    720,
    ...
};
```
In this line:
```
char* src_arr = "ABCDE";
```
you create a pointer to a string literal. It would be better to create just a static array:
```
static src_arr[] = "ABCDE";
```
And you can make it const since it never changes:
```
static const src_arr[] = "ABCDE";
```

Amazing, the details of such feedback kind of makes me sad about whether my self learning practices are any good. — Son Gohan
– Son Gohan, Commented Mar 3, 2020 at 0:36
The fact I did not hardcode the factorial was for the fact that I wanted it to be scalable for any length. — Son Gohan
– Son Gohan, Commented Mar 3, 2020 at 0:38
BTW I ran this on hackerrank and out of 48 test cases, 29 of them passed, for the other ones it basically says timed out, so I was wondering is it possible to make this more time and memory efficient ( given that I hardcode the factorial) ? — Son Gohan
– Son Gohan, Commented Mar 3, 2020 at 0:41
@SonGohan, 1) well, you actually can not make factorial computing to be scalable for any length (as long as you are not using bignum arithmetic). 2) permutation is a quite hard topic and I am not very good at it :), so I'd recommend you read the Wikipedia article about this topic and take a look at StackOverflow Questions. — eanmos
– eanmos, Commented Mar 3, 2020 at 8:54

Stack Exchange Network

Permutation code in C

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Permutation code in C

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions