Algorithmically Speaking - #8: Hidden Graphs in Permutations
Let me show you one of the best examples of graph theory problems I had the pleasure to attempt...
Hello there and welcome to another edition of Algorithmically Speaking.
Let’s talk about how graph theory arises in the most unexpected scenarios and how it can be a powerful tool to leverage in most circumstances.
Today, the topic will be similar to what we already covered here. The main difference is that today’s example will be more tricky but it will open up your mind for sure.
Let’s get started!
Swaps in Permutation
This is the rough statement of the problem:
Let’s say you are given a permutation of the numbers 1, 2, ..., n, and m pairs of positions (aj, bj).
At each step, you can choose a pair from the given positions and swap the numbers in that positions. What is the lexicographically maximal permutation you can get?
Let p and q be two permutations of the numbers 1, 2, ..., n. p is lexicographically smaller than q if a number 1 ≤ i ≤ n exists, so pk = qk for 1 ≤ k < i, and pi < qi.
To clarify the statement a little let’s look at the following image:
What we see here is a permutation of size 8. Which is no more than an array of the numbers from 1 to 8, in some order.
We are also given some pairs of values, which represent pairs of positions of the array that we can swap in one step. For example, we could have the following pairs for the permutation shown above:
The red dashed lines represent the pairs of positions whose elements can be swapped in one step. In this particular scenario, whose pairs are:
(1, 4)
(1, 5)
(6, 7)
(6, 8)
(7, 8)
Notice that these pairs refer to the positions of the array and not to the elements in those positions. For example, the pair (6, 7) represents the fact that the positions whose current values are 3 and 2, respectively, can be swapped in one step.
Lastly, we are asked to perform a series of swaps and create a permutation that is the lexicographically largest permutation possible that we can create, given this set of pairs.
But how do we know if the permutation we have is lexicographically larger than other permutations?
Let’s assume we are comparing two different permutations of the same size. According to the lexicographical criteria, the way to check which one is the largest is to iterate them from left to right until we find the first position where the corresponding values on each permutation are different. The permutation with a higher value is the largest one.
See an example in the image below:
With this comparison criteria, we can tell for example that the largest lexicographical permutation of size 8 is the one that lists every number from 1 to 8 in reverse order:
Now, the largest lexicographical permutation we can construct from the example permutation above, given the pairs of indices to swap is this blue permutation shown below:
Stop for a second here and try to think of a swap sequence you could perform to get the blue permutation in the image above from the initial permutation and the set of available pairs.
Most importantly, according to our comparison criteria, try to construct a permutation larger than the one I’m claiming is the largest.
The key issue to notice here is that, because the comparison criteria processes the elements from left to right and will stop once it finds the first differing positions, we need to place the largest elements as far to the left as possible.
But ok now, how do we solve the problem for a permutation of any size? And, where are the graphs I was going to show you, right?
Well, believe it or not, the graphs have been here since the beginning of the post. You just need to take a closer look.
Take the initial permutation, for example:
What if we interpret every position in this array as a node of a graph and every pair of indices that we can swap as an edge of this graph?
I think that the mere fact of asking you that question will make you look at the previous image from a different perspective. But here is a more clear example of the resulting graph from our example permutation:
Notice that the nodes of the graphs are labeled according to the indices of the array in the previous example, not according to the values. This means, for example, that the node with the label “4“ represents the position that has the value “8“ in the permutation.
One of the advantages of seeing this problem as a graph theory problem is that it shows the true power of the swap operations.
As individual swaps, they might not seem too useful. But when you realize that successive swaps extend to entire connected components you begin to understand things like the fact that every connected component of this graph can be treated independently.
So, if we can solve the problem for a connected component, we can then solve it for all of them and we will be solving it for the whole graph.
How to solve it, then?
Take a look at the previous graph, but now you will also see the values present in every position in the permutation:
I will leave this for you to prove but the main thing to notice here is that we can rearrange the values for any connected component in every possible way through successive swaps of adjacent nodes.
As we saw before, the optimal way to create a lexicographically largest permutation is to place the largest elements in the leftmost possible positions. This is what the optimal rearrangement looks like for this graph:
If you still don’t see it, place the nodes in a straight line following the order of the labels. You will get something like this:
Which in fact, coincides with the answer we got earlier:
I hope this example was as revealing for you as it was for me when I first tried to solve this problem.
In future posts, we will discuss functional graphs, also called permutation graphs, and have a lot to do with the topics we covered today.
Leave a comment showing examples of graph theory problems that you didn’t think were graph theory problems at first.
Last Words
I hope I was able to keep igniting your passion for Computer Science by showing you an example problem with multiple layers of analytical thinking and a beautiful solution using graphs.
In the next weeks, I will continue to show you more beautiful algorithmic challenges, this time related to geometrical concepts.
Lastly, I’m glad that the count of paid subscribers keeps growing as it shows that people care about keeping this publication alive. I will be sneaking bonus sections in some of the upcoming posts to reward those of you who decided to become paid members.
Thank you all for being here.
As always, if you think this post provides value for someone you know, share it with them. Nothing will make me happier.
See you next week,
Alberto
I really enjoyed this one(even the earlier posts but loved this one) , I just wish that if it were possible , you could go a bit more into the algorithmic parts as well? Superb series