Array of all permutations in C Is this a good compromise between readability and verbosity? Are there any bugs, additional error checking, or extraneous code as well?

// Generate permutations of array of n..n+x
// n must have no repetitions, sorted smallest to largest
// Steinhaus-Johnson-Trotter algorithm
// Results are not in lexicographical order

// Switch to using a generator when n! becomes too large. ~12 or 13 probably.

#include &lt;stdbool.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

enum directions { LEFT, RIGHT };

int **permute(int array[], int n);
bool mobile(int array[], int dir[], int count, int n);
void swap(int array[], int a, int b);

void printArray(int *array, int n, char c);
long long factorial(int n);

int **permute(int array[], int n) {
  if (n &lt; 1) {
    return NULL;
  }

  int bigInd;    // index of largest mobile num
  int bigNum;    // largest mobile num
  bool ismobile; // If there is still a mobile number
  int counter = 0;

  int fact = factorial(n);

  int *dir;
  int **res;
  if ((dir = malloc(n * sizeof(int))) == NULL) {
    fprintf(stderr, "Error allocating memory\n");
    exit(EXIT_FAILURE);
  }
  for (int i = 0; i &lt; n; i++) {
    dir[i] = LEFT;
  }

  if ((res = malloc(fact * sizeof(int *))) == NULL) {
    fprintf(stderr, "Error allocating memory\n");
    exit(EXIT_FAILURE);
  }
  for (int i = 0; i &lt; fact; i++) {
    if ((res[i] = malloc(n * sizeof(int))) == NULL) {
      fprintf(stderr, "Error allocating memory\n");
      exit(EXIT_FAILURE);
    }
  }

  while (1) {
    memcpy(res[counter], array, n * sizeof(int));
    counter++;
    bigInd = 0;
    bigNum = 0;
    ismobile = false;
    for (int i = 0; i &lt; n; i++) {
      if (mobile(array, dir, n, i)) {
        ismobile = true;
        if (array[i] &gt; bigNum) {
          bigInd = i;
          bigNum = array[i];
        }
      }
    }
    if (!ismobile) {
      break;
    }
    if (dir[bigInd] == LEFT) {
      swap(array, bigInd, bigInd - 1);
      swap(dir, bigInd, bigInd - 1);
    } else {
      swap(array, bigInd, bigInd + 1);
      swap(dir, bigInd, bigInd + 1);
    }

    for (int i = 0; i &lt; n; i++) {
      if (array[i] &gt; bigNum) {
        dir[i] = !(dir[i]);
      }
    }
  }

  free(dir);
  return res;
}

void swap(int array[], int a, int b) {
  int temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

bool mobile(int array[], int dir[], int count, int n) {
  if ((n == 0 &amp;&amp; dir[n] == LEFT) || (n + 1 == count &amp;&amp; dir[n] == RIGHT) ||
      (dir[n] == RIGHT &amp;&amp; array[n + 1] &gt; array[n]) ||
      (dir[n] == LEFT &amp;&amp; array[n - 1] &gt; array[n])) {
    return false;
  }
  return true;
}

void printArray(int array[], int n, char c) {
  if (!array || n &lt; 1) {
    return;
  }
  for (int i = 0; i &lt; n; i++) {
    printf("%d", array[i]);
  }
  printf("%c", c);
}

long long factorial(int n) {
  long long result = 1;
  for (long long i = n; i &gt; 1; i--) {
    result *= i;
  }
  return result;
}

int main(void) {
  int a[] = {1, 2, 3, 4, 5};
  int length = sizeof(a) / sizeof(a[0]);
  int fact = factorial(length);
  int **r = permute(a, length);
  for (long long i = 0; i &lt; fact; i++) {
    printf("%*lld: ", 3, i + 1);
    printArray(r[i], length, '\n');
  }
  for (long long i = 0; i &lt; fact; i++) {
    free(r[i]);
  }
  free(r);
}
verbose vs readable

Why choose?

Just encapsulate all the explicit code and error checkings into functions (if possible) or macros (only when functions can't do it), and have a clean high level function.



Safe usage of malloc()

Malloc is easily misused.  Problems using malloc are the following:


sizeof(type) vs sizeof(*foo):


foo = malloc(sizeof(*foo) * nmemb); is better because if you ever change the type of foo, this call will still be valid, while if not, you would have to change every line where malloc is called with foo.  If you forget any of those lines, good luck!


overflow:


If (sizeof(*foo) * nmemb) &gt; SIZE_MAX, it will silently wrap around, and allocate a very small amount of memory, and you will most likely end up accessing memory that you shouldn't.

Solution:

Use this enclosure around malloc



sizeof(type) vs sizeof(*foo)

As I said above, use the second.  Apart from malloc you also have this problem in memcpy.



fprintf(stderr, ...) + exit()

You could combine those two in just one function call:

error(): GNU extension

err(): BSD extension

I would advise to use the first one: first, GNU extensions are more commonly available (even Clang has most (if not all) of them); second, because err is a common name used in temporary variables or labels used in case of an error.



C99 types

If you don't have a reason to use old C89 (yes, 1989) types, don't use them. What is long long, and why would you use it?

int64_t is clearer, shorter, and better in every way, unless you need to interface a library that hasn't been updated in the last 30 years, which ironically is most of them.

Also instead of int, use int32_t, although if you want factorials that fit into an int64_t, I don't think you need more than int8_t.