Best way to hash ordered permutation of [1,9]

Question

I'm trying to implement a method to keep the visited states of the 8 puzzle from generating again.
My initial approach was to save each visited pattern in a list and do a linear check each time the algorithm wants to generate a child.
Now I want to do this in O(1) time through list access. Each pattern in 8 puzzle is an ordered permutation of numbers between 1 to 9 (9 being the blank block), for example 125346987 is:

1 2 5
3 4 6
_ 8 7

The number of all of the possible permutation of this kind is around 363,000 (9!). what is the best way to hash these numbers to indexes of a list of that size?

Answer 1

First. There is nothing faster than a list of booleans. There's a total of 9! == 362880 possible permutations for your task, which is a reasonably small amount of data to store in memory:

visited_states = [False] * math.factorial(9)

Alternatively, you can use array of bytes which is slightly slower (not by much though) and has a much lower memory footprint (by a power of magnitude at least). However any memory savings from using an array will probably be of little value considering the next step.

Second. You need to convert your specific permutation to it's index. There are algorithms which do this, one of the best StackOverflow questions on this topic is probably this one:

Finding the index of a given permutation

You have fixed permutation size n == 9, so whatever complexity an algorithm has, it will be equivalent to O(1) in your situation.

However to produce even faster results, you can pre-populate a mapping dictionary which will give you an O(1) lookup:

all_permutations = map(lambda p: ''.join(p), itertools.permutations('123456789'))
permutation_index = dict((perm, index) for index, perm in enumerate(all_permutations))

This dictionary will consume about 50 Mb of memory, which is... not that much actually. Especially since you only need to create it once.

After all this is done, checking your specific combination is done with:

visited = visited_states[permutation_index['168249357']]

Marking it to visited is done in the same manner:

visited_states[permutation_index['168249357']] = True

Note that using any of permutation index algorithms will be much slower than mapping dictionary. Most of those algorithms are of O(n²) complexity and in your case it results 81 times worse performance even discounting the extra python code itself. So unless you have heavy memory constraints, using mapping dictionary is probably the best solution speed-wise.

Addendum. As has been pointed out by Palec, visited_states list is actually not needed at all - it's perfectly possible to store True/False values directly in the permutation_index dictionary, which saves some memory and an extra list lookup.