MASTERB4APRIL's blog

By MASTERB4APRIL, 17 months ago, In English

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! :)

  • Vote: I like it
  • +55
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Great job bro 3>

Do NOT think twice before sharing such a great blog next time :D

»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Incidentally, I was just trying to solve a problem now, which I couldn't, and checked the editorial. I didn't understand it completely and luckily saw your post. And you literally explained the same.Thanks for the explanation.
1768D - Lucky Permutation was the question.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't get how to use this POV;

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to count how many loops Apply the permutation multiple times until you reach the position where you started For example: P[5] = 1 P[1] = 3 P[3] = 5 The size of this loop is 3 Also, don't forget to mark the visited numbers so you don't count some ring twice

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can use this idea for 1787F I believe