current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite

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);
}
share|improve this question
1  
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. – CiaPan Feb 10 at 7:57
    
Sorry I just read the article partially. – NoobCoder Feb 23 at 2:30
up vote 4 down vote

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.

share|improve this answer
up vote 2 down vote

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++) {
share|improve this answer
    
Thankyou. I will change that immediately. Do you know if gcc compiler will be smart to do that while compiling? – NoobCoder Feb 10 at 6:02
    
@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. – JS1 Feb 10 at 7:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.