4
\$\begingroup\$

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 <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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 < 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 < 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 < 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 < n; i++) {
      if (mobile(array, dir, n, i)) {
        ismobile = true;
        if (array[i] > 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 < n; i++) {
      if (array[i] > 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 && dir[n] == LEFT) || (n + 1 == count && dir[n] == RIGHT) ||
      (dir[n] == RIGHT && array[n + 1] > array[n]) ||
      (dir[n] == LEFT && array[n - 1] > array[n])) {
    return false;
  }
  return true;
}

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

long long factorial(int n) {
  long long result = 1;
  for (long long i = n; i > 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 < fact; i++) {
    printf("%*lld: ", 3, i + 1);
    printArray(r[i], length, '\n');
  }
  for (long long i = 0; i < fact; i++) {
    free(r[i]);
  }
  free(r);
}
\$\endgroup\$

2 Answers 2

Reset to default
3
\$\begingroup\$

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) > 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.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you. I haven't done much proper programming for a couple of decades, so this gives me some guidance on where to focus on practicing for awhile and fixing old bad habits. The systems used for compilation are _WIN64 and Linux, hence fprintf. \$\endgroup\$ Commented Jul 15, 2019 at 19:23
1
\$\begingroup\$

Possible Bugs
In main() there is an assignment from a fuction that returns long long (factorial) to an integer variable (fact). This may result in errors depending on the word size of int. One of the possibilities is a positive long long value can be converted to a negative integer. Since there is a comparison between the variable fact and another long long value (the loop control variable i) it would be better if fact was declared as long long.

Reducing Verbosity
To reduce the verbosity it might be better to move the functions swap, mobile, printArray and factorial before the function permute and delete all the function prototypes.

The variable names bigInd and bigNum can be confusing it based on the comments and to remove the need for the comments perhaps bigInd could renamed indexLargestMobileNumber and bigNum could be renamed largestMobileNumber. I initialy confused bigInd with big Endian. It is also not clear why dir and res are named dir and res.

Array Memory Allocation
When allocation memory for arrays in the C programming language it might be better to use calloc(size_t SIZE_OF_ARRAY, size_t SIZE_OF_ELEMENT); for 2 reasons, the first is it is obvious that array is being allocated, and the second is that calloc() zeros out all the elements of the array. This means that in the function permute this for loop would not be necessary

for (int i = 0; i < n; i++) {
    dir[i] = LEFT;
}

The calloc() function will perform better than the preceeding for loop. If the code continues to use malloc() rather than calloc it might be better to use memset() since this will also out perform the previous for loop.

Complexity
The function permute() is complex and it may be better to break it down into sub-functions where some of the code my be reusable.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ An old bad habit of keeping names to a max of 6 or 8 chars I suppose. Big Endian didn't even occur to me since it's been awhile since I used a z series or the like. Is there any common consensus on variable name length sizes? dir and res will be changed to direction and results. \$\endgroup\$ Commented Jul 15, 2019 at 19:30
  • \$\begingroup\$ @smp It's been a long time since fortran 66 or basic that limited the length of variable names. I'm not aware of a common consensus. \$\endgroup\$ Commented Jul 15, 2019 at 21:35
  • \$\begingroup\$ @smp Use very explicit names in globals (actually, avoid globals;), and use the shortest while still memorable names for locals. If there are still possible confusions, it's probably that the function is too long and should probably be divided \$\endgroup\$ Commented Jul 15, 2019 at 23:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.