Some people face difficulties in dealing with permutations. That's because they don't know what they really tell us.

A permutation is any list of objects that have multiple arrangements, for example:

& % # !

! # & %

! & % #

It doesn't necessarily have to be a sequence of numbers from 1 to n, you can just say that

92 45 23 52

45 92 52 23

are different permutations of some objects.

Let's say we can only perform a swap between two objects, and we want to sort a permutation according to the sizes of our objects.

1 3 4 2 --> 1 2 4 3 --> 1 2 3 4

We aim at finding the minimum number of swaps to do so.

We can view this problem as we want to place each object in a desired position, i.e., 1 has to be in the position 1, 2 has to be in the position 2, etc.

If we have considered the positions as boxes and each object must return to its box, it might have created a visually simple graph:

Where each edge points to where the object of that box is located. Like when you want to link some wires to some sockets.

The only difficulty is that you can't swap more than two wires at once. We observe easily, since each node has one outgoing edge and one incoming edge, that our graph is some closed rings:

We want each node to be connected to itself. The best swap can change the connections between adjacent nodes that can separate on node from its ring:

Therefore, the minimum number of swaps to achieve that goal is the sum of (ring's size minus 1).

Which is: (number of nodes) — (number of rings)

This is my first entry. I know that I haven't discovered something new, but I think it worths sharing.

Thanks for reading! :)