mike mike - 23 days ago 7
Java Question

Using Boolean to Identify/Segregate elements of array (java)

I'm a novice student of coding and learning via codefights.org, among other resources. I stumbled upon this problem:

======

Find the number of cycles of a given permutation.

Example

For permutation = [1, 3, 2, 6, 4, 5], the output should be
permutationCycles(permutation) = 3.*

int permutationCycles(int[] permutation) {

boolean[] inCycle = new boolean[permutation.length];
int result = 0;

for (int i = 0; i < permutation.length; i++) {
if (!inCycle[i]) {
int position = i;
while (!inCycle[position]) {
inCycle[position] = true;
position = //...// ;
}
result++;
}
}

return result;
}


The task is to replace the //...// with the right code. I can code this in my own way but without using a boolean array. What I don't understand is how the boolean array inCycle is connected to the permutation array. Can someone also explain to me what the if loop here means? Thanks in advance.

Answer

If I understand the question, it should be

position = permutation[position]  - 1;

This brings you to the next element of the current cycle. I used permutation[position] - 1 and not permutation[position] because the indices in your example begin in 1, while Java arrays are 0 based.

The boolean array is used to mark which elements were already visited (and therefore belong to some cycle you already counted).

For the permutation [1, 3, 2, 6, 4, 5], the execution goes like this :

i == 0
    position = 0
    position = permutation [0] - 1 = 0 -> this closes the first cycle
i == 1
    position = 1
    position = permutation [1] - 1 = 2
    position = permutation [2] - 1 = 1 -> this closes the 2nd cycle
i == 2 already in cycle
i == 3
    position = 3
    position = permutation [3] - 1 = 5
    position = permutation [5] - 1 = 4
    position = permutation [4] - 1 = 3 -> this closes the 3rd cycle
i == 4 already in cycle
i == 5 already in cycle