Character permutations - Revisited

Several hours ago I posted this question about Generating character permutations in Python.

User rolfl said that my main problem was not using the right tool for the job, as Python is interpreted it will be much slower than a compiled solution. So I tried to write this in C.

Objective

Generate a file containing all fixed length l permutations of a given set of chars, in this case upper-case alphabet.

i.e.: With l = 5 the output file should look like:

AAAAA
AAAAB
AAAAC
...
ZZZZZ

My solution

I used a recursive for loop. It's my first program in C (after a hello world) so I don't know what it's worth. It runs in about 2.621s on my 2.9 GHz Intel Core i7

#include 

FILE *fp;

char alphabet[26] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
int len = 5;

void recloop(char *pwd, int repeat) {
  int i;
  for (i = 0; i < 26; i++) {
    pwd[len-repeat] = alphabet[i];

    if (repeat == 1) {
      fprintf(fp, "%s\n", pwd);
    }
    else {
      recloop(pwd, repeat - 1);
    }
  }
}

int main(void) {
  char pwd[len];
  fp = fopen("output", "w");
  recloop(pwd, len);
}

A few notes:

-
You aren't declaring alphabet in a very readable and maintainable form. Here's how I would do it:

static const char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

As you can see, I also made this variable static and const. static renders variable local to the file, and const makes it so that we can't screw with the array somewhere along the line (and also makes things a tidbit faster). This leads me to my next point...

Also, you don't have to specify the number of elements in the array when you declare it like this, since the compiler can determine that itself (because it is constant).

-
fp and len are global variables when they shouldn't be. Arguably alphabet shouldn't be one either, but I think it is find as long as you have the static in front of it. Anyways, they should be declared as local variables and then passed to the functions that need them.

-
I'm not sure your algorithm is the most optimal. I used a method known as "backtracking" myself, which seems to be the most efficient that I could find in practice.

-
fprintf() isn't going to be as efficient compared to fwrite(). I would consider rewriting your code if you still want to generate a permutation table.

Time test (without compiler optimizations)

mycode.c:

#include 
#include 
#include 

static const char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
static const int alphabetSize = sizeof(alphabet) - 1;

static void bruteImpl(char* str, size_t index, size_t maxDepth)
{
    for (size_t i = 0; i < alphabetSize; ++i)
    {
        str[index] = alphabet[i];

        if (index == maxDepth - 1); //printf("%s\n", str);
        else bruteImpl(str, index + 1, maxDepth);
    }
}

void bruteSequential(size_t maxLen)
{
    char* buf = calloc(maxLen + 1, sizeof(char));

    for (size_t len = 1; len <= maxLen; ++len)
    {
        bruteImpl(buf, 0, len);
    }

    free(buf);
}

int main(void)
{
    bruteSequential(5);
}

$ gcc opCode.c # I took out your fprintf call so that it wouldn't be a factor
$ time ./a.out

real 0m0.170s
user 0m0.139s
sys 0m0.009s

$ gcc mycode.c
$ time ./a.out

real 0m0.043s
user 0m0.039s
sys 0m0.002s


StackExchange Code Review Q#67466, answer score: 4