A few remarks in addition to ccoakley's nice answer and stubbscroll's comment, concerning the specific example and a few general principles.
Regarding stubbscroll's remark that this particular problem has only 9! = 362880 different states:
One (fairly easy) way to encode permutations as numbers is indexing the permutations by lexicographic ordering. For example
0 1 2 3 --> 0
0 1 3 2 --> 1
0 2 1 3 --> 2
...
1 0 2 3 --> 6
1 0 3 2 --> 7
...
3 1 2 0 --> 21
3 2 0 1 --> 22
3 2 1 0 --> 23
The trick is writing the index in factorial base,
n = a_1 * 1! + a_2 * 2! + a_3 * 3! + a_4 * 4! + ...
where 0 <= a_k <= k. If you have s symbols, the indices range from 0 to s!-1, so you have s-1 coefficients in the factorial-base expansion of n, (a_1,a_2,...,a_(s-1)). The permutation with index n is then found as follows
for i = 1 to s-1
the i-th symbol becomes the (a_(s-i)+1)-th smallest unused symbol
the last symbol is the left over one
Since that's not particularly clear, an example. Say we look for the permutation with index 4231 of {1,2,3,4,5,6,7,8}. First we expand 4231 in factorial base
4231 = 1 + 2*2115 : a_1 = 1
2115 = 0 + 3* 705 : a_2 = 0
705 = 1 + 4* 176 : a_3 = 1
176 = 1 + 5* 35 : a_4 = 1
35 = 5 + 6* 5 : a_5 = 5
5 = 5 + 7* 0 : a_6 = 5
all further coefficients (here just a_7) are 0. It's better to follow writing the a_i in reverse order, (a_7,a_6,...a_1), so
coefficients symbols choice
0,5,5,1,1,0,1 1,2,3,4,5,6,7,8 1
5,5,1,1,0,1 2,3,4,5,6,7,8 7
5,1,1,0,1 2,3,4,5,6,8 8
1,1,0,1 2,3,4,5,6 3
1,0,1 2,4,5,6 4
0,1 2,5,6 2
1 5,6 6
- 5 5
Result: 17834265.
Find the index of 246351:
symbols count perm index(head)
1,2,3,4,5,6 6 2,4,6,3,5,1 1 a_5 = 1
1,3,4,5,6 5 4,6,3,5,1 2 a_4 = 2
1,3,5,6 4 6,3,5,1 3 a_3 = 3
1,3,5 3 3,5,1 1 a_2 = 1
1,5 2 5,1 1 a_1 = 1
index is `1*5! + 2*4! + 3*3! + 1*2! + 1*1! = 187.
So now we have a fairly simple way of converting between permutations and their indices. The conversion isn't super fast (O(s^2)), but you get easy and fast comparison and lookup (have I seen the state before?). Whether it's a gain remains to be decided in each case.
Now, for the particular case at hand, we have some further restrictions reducing the search space.
- Each move is a cyclic permutation of three elements, thus an even permutation.
Hence all combinations of such moves are also even permutations, meaning half of the possible states are unreachable. We are left with (at most) 9!/2 = 181440 reachable states. Indexing even permutations by lexicographic ordering is only slightly more complicated. The crucial point is that a permutation is even if and only if the sum of the coefficients a_k in the factorial-base expansion of its index is even.
Reduce the search space using constraints and symmetries. If you're employing a search strategy using a structure with all possible states, this will reduce the memory requirements by a corresponding factor. If your search strategy only touches reachable states, the constraints don't reduce the number of steps, but they can still speed up the search due to the lower memory footprint. The use of symmetries can reduce the number of steps by identifying equivalent states.
In the example problem, we have the further nice situation that the 5 is already in the correct place, and that an optimal solution doesn't move it ever. So we need only consider even permutations of 8 symbols, reducing the search space to 8!/2 = 20160 possible states. (Though that is not obvious.)
In general, however, it is difficult to prove that an optimal solution never leaves a particular subset of the possible states, so you can rarely directly impose such a restriction to your search.
But it is often the case that you can find a good solution of the problem using such a restriction and then use the good solution to prune early in your search for the optimal solution in the unrestricted search space.
A variant one can often use is finding an approximation by a greedy strategy and using this as a bound to prune early in an exhaustive search.
