# Count number of cycles in permutation

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

• Do you have a sample input file? – Josiah Jun 15 '18 at 6:19
• @Josiah Edited the question with an example. – Itay4 Jun 15 '18 at 6:24

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;
}
}
}
}


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.

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