Count number of cycles in permutation

Question

Write a function that a receives file name and an integer N as arguments, that represent a binary file which contains N integers, which constitute a permutation. Return the number of cycles in the permutation.

Code

int countCyclesHelper(int* array, int N) {
  int i, first, current, temp, counter = 0;
  for (i = 0; i < N; i++) {
    first = i;
    current = first;
    while (1) {
      if (array[current] == -1) {
        break;
      }
      temp = array[current] - 1;
      array[current] = -1;
      current = temp;
      if (current == first) {
        counter++;
        break;
      }
    }
  } 
  return counter; 
}

int countCycles(char *name, int N) {
  char *buffer = (char*)malloc(N);
  int *array = (int*)malloc(N);
  int i, numberOfCycles;
  FILE *fp = fopen(name, "rb");
  fread(buffer, sizeof(buffer), 1, fp);
  for (i = 0; i < N; i++) {
    array[i] = buffer[i] - '0';
  }
  numberOfCycles = countCyclesHelper(array, N);
  free(buffer);
  free(array);
  fclose(fp);
  return numberOfCycles;
}

Example

Input (test.bin):

54321

Output:

3

Any review is appreciated.

Answer 1

Unless you use a very old compiler, I suggest you to declare (and initialize) variables as late as possible and limit their scope. This prevents potential mistakes like

return current; /* whoops, meant counter! */

in countCyclesHelper.

Next, unless you got invalid input, only array[first] may be -1, otherwise one of your nodes in your (implicit) graph has two incoming edges and the original file didn't contain a valid permutation.

If we take both suggestions into account, we end up with the following countCyclesHelper:

int countCyclesHelper(int* array, int N) {
  int total_cycles = 0;

  for (int i = 0; i < N; i++) {
    const int first = i;
    int current = first;

    if (array[current] == -1) {
      /* already counted this cycle */
      continue;
    }

    while (1) {
      const int temp = array[current] - 1;
      array[current] = -1;
      current = temp;
      if (current == first) {
        counter++;
        break;
      }
    }
  } 
  return total_cycles; 
}

While I kept first, it's possible to replace it with i.

---

As you can see, I've added const at various places. If we don't intend to change a value it's usually a good idea to prevent it with const. This holds for example for your name in countCycles. We don't want to accidentally change the file name:

int countCycles(const char *name, int N)

Next, fread(buffer, sizeof(buffer), …) is—unfortunately—wrong, since buffer is a pointer. You end up with fread(buffer, sizeof(char*), …). Therefore, your program contained undefined behaviour, unless N <= sizeof(char*).

That being said, countCycles is an overkill, since you handle only single digit permutation indices. For any N >= 10the content ofarraywon't be a permutation. With this in mind, we can simplifycountCycles` a lot:

enum { MAXIMUM_DIGITS = 9 };

int countCycles(const char *name, int N) {
  if(N <= 0 || N > MAXIMUM_DIGITS) {
    return -1;
  }

  char buffer[MAXIMUM_DIGITS];

  FILE *fp = fopen(name, "rb");
  if(fread(buffer, N, 1, fp) != N) {
    fclose(fp);
    return -1;
  }
  fclose(fp);

  int array[MAXIMUM_DIGITS];

  for (int i = 0; i < N; i++) {
    array[i] = buffer[i] - '0';
  }
  return countCyclesHelper(array, N);
}

If MAXIMUM_DIGITS gets larger at some point, you probably need to switch to malloc again, but simple arrays with a static size work well enough for your use case.

Answer 2

• Do not cast what malloc returns. It may lead to hard to find errors.

• If N is greater than 256, array cannot constitute a permutation. Otherwise, there is no reason for array to exists; you can operate directly on buffer.

• It seems that the array indexing is 1-based (if so, it must be clearly stated in the problem statement). The code however treats indexing as 0-based, leading to the very confusing subtraction temp = array[current] - 1.

  A cleaner approach is to explicitly convert the array to 0-based, eg:

  void rebase_to_0(int * array, int N) {
      for (int i = 0; i < N; i++) {
          array[i] -= 1;
      }
  }
  

• first and i are synonymous; there is no need to have both.

• You may want to verify that the input indeed represents a permutation.