mike mike - 11 months ago 59
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 Source

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