Mapping a permutation to a number has attracted much social concern. In shortest-path problems, in case a node (or state) is a permutation, we should convert states to integers, in order to BFS or Dijkstra on new graph comfortably. Many coders have known using std::map or trie to do this work. However, both have certain disadvantages. My writing will introduce a new way to solve this problem.
It is hard to write both long and detailed blog. Therefore, you can comment anything which you didn't understand well. I will reply (or update this blog if it is necessary).
To understand the role of mapping a permutation to a number, consider problem POSLOZI from COCI. Our goal is to find the length of the shortest path from a permutation S to an other permutation T using allowed operations. A valid operation is swapping two elements in the permutation. We are given a list of pair (p, q) denote we can swap the element indexed p and the element indexed q. Any other swapping operations are not allowed. A possible strategy is to BFS simultaneously from both S and T.
.
