mike - 7 months ago 47

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

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

Source (Stackoverflow)