mike - 1 year ago 67

Java Question

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
```