Generate all permutations in C

Question

I have written code for generating all the permutations in C as explained here. How can the code be optimized? Are there any memory leaks?

int factorial(int n) {
 int fact = 1;
 for(int i = 2; i <= n; i++)
 fact *= i;
 return fact;
}
int main(){
 int len = 4, i, j;
 int **p;
 int **q = (int**) malloc(sizeof(int*));
 q[0] = (int*) malloc(sizeof(int));
 q[0][0] = 1;
 for(i = 0; i < len; i++){
 p = (int**) malloc(sizeof(int*) * factorial(i + 1));
 for(j = 0; j < factorial(i + 1); j++)
 p[j] = (int*) malloc(sizeof(int) * (i + 1));
 int y=0;
 for(j = 0; j < factorial(i); j++){
 for(int k = 0; k < i + 1; k++){
 int added = 0;
 for(int l = 0; l < i + 1; l++){
 if(k == l){
 p[y][l] = i + 1;
 added = 1;
 }
 else
 p[y][l] = q[j][l-added];
 }
 y++;
 }
 }
 for(j = 0; j < factorial(i); j++)
 free(q[j]);
 free(q);
 q = p;
 }
 for(i = 0; i < factorial(len); i++){
 for(j = 0; j < len; j++)
 printf("%d\t", p[i][j]);
 printf("\n");
 free(p[i]);
 }
 free(p);
}

• CiaPan: This code does not implement the algotihm described there The algorithm described there requires only one array of numbers, possibly with accompanying parallel array of boolean indicators of 'travelling left' / 'travelling right'. The whole bunch of factorial(i + 1) arrays allocated and appended into p[] array has nothing to do with the described Johnson-Trotter algorithm.
• NoobCoder: Sorry I just read the article partially.

Answer 1

This code is far from readable.

---

Optional braces should not be considered optional.

Omitting these braces leaves your code prone to future errors.

Besides this, I personally find it makes your code harder to parse. I'm so used to seeing loop bodies (or if/else) contained within braces, that it becomes easy to mentally skip that block and say "Yup, this is the looping stuff that's happening." Here, without the brackets, it just looks like your code has indentation problems, and it is distracting.

---

Single-letter variable names are not acceptable.

The only place that they're even remotely acceptable is as for loop iteration variables, and even this is a purely historical exception to the rule (and I'd argue that i and j are in violation of this exception as they're not declared within the for loop's initialization statement).

• Small variable names don't make your code run faster.
• Small variable names don't make your code use less memory.
• Small variable names don't make your code compile faster.
• Small variable names don't make your executable size smaller.
• Small variable names do make your code harder to read.

An amazing example of this last point is your code base where we have six different single letter variable names all in the same scope (plus another two in the factorial function).

To the compiler, it doesn't matter what you name all of your variables. It's smart enough to keep up with all of them. I'm not that smart. I'm looking at six variables with completely meaningless names that I'm expected to keep track of.

A variable's name should tell the human reader exactly what it is meant to store.

---

It's called main. It's not called everything.

You did manage to move the factorial function out. But there's a lot of complexity remaining in main that can surely be refactored out into smaller, bite-size functions that can be good names to explain exactly what they're doing. And that'd definitely help with your code's readability.

Answer 2

Recomputing the same thing over and over

You have a bunch of lines like this in your program:

for(i = 0; i < factorial(n); i++){

Let's count how many multiplies you need to finish this loop. The loop runs for \$n!\$ iterations. Each loop iteration calls factorial(n), which requires \$n-1\$ multiplies. In total, you need \$n! * (n-1)\$ multiplies. For n=10, you would be doing over 32 million multiplications, when you only need 9:

count = factorial(n);
for (i = 0; i< count; i++) {

• NoobCoder: Thankyou. I will change that immediately. Do you know if gcc compiler will be smart to do that while compiling?
• JS1: @NoobCoder It might be able to optimize that because your factorial function is in the same file. But it's better to just avoid using function calls like that in loop expressions.