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.

. .

1. Disadvantages of std::map and trie

In the first place, what I put in my priority is inefficiency of wide-known methods. Std::map has big time complexity, and trie demands a quite long conding-time. 1, Using std::map is the easiest way to code but it costs big complexity, i.e. O(logN * L) for each query (where L is length of the permutation, N is number of permutations, in other words N = L!). 2, Trie brings us the speed in queries but it uses quite much memory O(N * L) and requests a long time to code. Therefore, both std::map and trie are not perfect solutions. It encourages me to find a better solution.

2. My new method

In the second place, I will talk about my method treating this problem. Assume length of permutations L = 11. We will use a 7-directional array to map first 7 elements to a number, called C1.

int C1[11][11][11][11][11][11][11];
int MaxC1=0;

At this point, the number associate with the first 7 elements of permutation P is C1[P₀][P₁][P₂][P₃][P₄][P₅][P₆].

For the first 7 elements, we have 11! / 4! = 1663200 states. There are 4 remaining elements.

Now first let's talk about a naive solution, we will create array C2 declared as following:

int C2[1663200+1][11][11][11][11];
int MaxC2=0;

In order to get the number associate with the permutation P, we will use following function:

int index(const vector<int> &P) {
  int &I1 = C1[P[0]][P[1]][P[2]][P[3]][P[4]][P[5]][P[6]];
  if (I1==0) I1=++MaxC1;
  int &I2 = C2[I1][P[7]][P[8]][P[9]][P[10]];
  if (I2==0) I2=++MaxC2;
  return I2;
}

We have already created function index to map a permutation to a number (although it is not efficient in memory yet). If you have not understood well, please read again carefully what I wrote before continuing reading.

You may realize that size of C1 is ok but C2 is too large. Now we need to make C2 smaller. When 7 elements are determined, we can use the relations (6 relations of 6 pairs of 4 elements) between the 4 remaining elements to represent them (remaining elements). Let x = P₇, y = P₈, z = P₉, t = P₁₀ . Instead of using C2[I2][x][y][z][t], we will use C2[I2][x > y][x > z][x > t][y > z][y > t][z > t] instead. This makes the size of C2 become 1663200 * 64 instead of 1663200 * 11⁴.

The final implementation is here:

int C1[11][11][11][11][11][11][11]; // 77MB
int MaxC1=0;
int C2[1663200+1][2][2][2][2][2][2]; // 425 MB
int MaxC2=0;

int index(const vector<int> &P) {
  int &I1 = C1[P[0]][P[1]][P[2]][P[3]][P[4]][P[5]][P[6]];
  if (I1==0) I1=++MaxC1;
  int x=P[7], y=P[8], z=P[9], t=P[10];
  int &I2 = C2[I1][x>y][x>z][x>t][y>z][y>t][z>t];
  if (I2==0) I2=++MaxC2;
  return I2;
}

3. Effectiveness

In the third place, what cannot be left out is the effectiveness of my method.

Time complexity

The time complexity of function index is O(L) (to access), and the constant is quite small.

Memory complexity

The memory is quite big but acceptable. If you cannot accept this memory size, you can use 3 or 4 array (C1, C2, C3, C4, …) to reduce the memory size.

Coding time

Personally, function index is short and easy to code in a little time.

Effectiveness in DP

Assume you are using function dp(u) (which u is a permutation), you can reduce a bool array. To determine if f(u) is calculated, just check if C2[I1][x>y][x>z][x>t][y>z][y>t][z>t] is zero or not.

4. Magic numbers

Lastly, selected magic numbers is note-worthy. I will talk about reasons why I split 11 elements into 2 groups: first 7 elements and last 4 elements. Because I want to use only two array C1 and C2, I must write 11 into a sum of two number, such ways are: 11=10+1=9+2=8+3=7+4=6+5, and I found that 7+4 is the best selection. 8+3 is impossible because size of C1 is too large: 11^8 ints = 857 MB. 6+5 is not good because size of C2 is too large, 936 MB. Therefore 7+4 is reasonable. More notably, if I use [x][y>z][y>t][z>t] instead of [x>y][x>z][x>t][y>z][y>t][z>t], the size will be 11*2^3 (=88) instead of 2^6 (=64). You should consider those magic numbers carefully to balance the memory used.

To handle problems with L=12, in a naive view point, we can't use any data structure (even trie) because 12! ints = 1.9GB (too big). However, not all of states are reached. In problem POSLOZI, there are less than 10^7 reached states. This is my code http://paste.ubuntu.com/9686778/. It passed 9/10 tests and runs the last test in 3 seconds. It is what I expected because my strategy is not the perfect solution (someone said the optimal one is to use A* with some heuristics).

Conclusion

In summarize, for all the mentioned advantages above, the new method shows us a good efficiency. I highly recommend that you should carefully consider writing to make good decision on problem mapping a permutation to a number.

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).