2
\$\begingroup\$

I am making a permutation generator in c. Any ideas how I can make it faster?

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

int main(int argc, char *argv[]){
    char s[] = "abcdefghijklmnopqrstuvwxyz";
    int n = 8, c[n], i, l = strlen(s);
    char w[n];

    for(i = 0; i < n; i++){
        c[i] = 0;
        w[i] = '\0';
    }
    w[n] = '\0';
    while(c[0] < l){
        for(i = 0; i < n; i++){
            w[i] = *(s + c[i]);
        }
        printf("%s\n", w);
        c[n - 1] += 1;
        for(i = n - 1; i >= 0; i--){
            if(c[i] > l - 1 && i != 0){
                c[i] = 0;
                c[i - 1] += 1;
            }
        }
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Especially after JS1's suggestion, you're print bound. I time at least 90% of the runtime being in printing after my suggestion. I've no doubt buffering can improve that, but it seems like a waste to try. "how I can make it faster?" probably isn't a useful question. \$\endgroup\$
    – Veedrac
    Jan 23, 2016 at 21:03
  • \$\begingroup\$ If I undestand the problem correctly, you're trying to print all 8-char strings built with 26-letter alphabet without repetitions? If so, you're going to print about 2.5 times 10^15 strings... \$\endgroup\$
    – CiaPan
    Jan 23, 2016 at 21:33

2 Answers 2

2
\$\begingroup\$

Buffer overrun

Your array w should be one larger than it currently is to hold a null terminating character. Otherwise when you write to w[n] you are writing past the end of the array.

Excess copying

Currently, every time you generate a new permutation, you rewrite all of the w array. You actually only have to rewrite the parts that changed since the last permutation. To do this, you should write to w[i] only when c[i] changes. So for example:

while(c[0] < l){
    c[n - 1] += 1;
    w[n - 1] = s[c[n - 1]];
    for(i = n - 1; i >= 0; i--){
        if(c[i] > l - 1 && i != 0){
            c[i] = 0;
            w[i] = s[0];
            c[i - 1] += 1;
            w[i - 1] = s[c[i - 1]];
        }
    }
}

Alternate implementation

If you are looking to find a faster way to generate permutations, I suggest you look at this codereview question and in particular my answer to it.

\$\endgroup\$
1
\$\begingroup\$

Once you fix the buffer overrun, a quick improvement is to write

w[n] = '\n';

and then print with

fwrite(w, sizeof(char), n + 1, stdout);

Also, remember to #include <string.h>.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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