mike - 1 year ago 95
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.

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download