Problem Detail: I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys. Given that I know how all the keys look up front, it seems I that there should be an optimal hashing function, and an optimal size of the table to store the values in. Is this true? If so, how can I create the perfect hashing function? And also, how can I determine the optimal size for the hash table? update: I’m looking to store all of the possible permutations, where each will be stored only once, which means the table should in the end contain exactly all 362 880 keys (since I have a hard limit on my algorithm for which I need to optimize my worst case scenario.)
Asked By : Jakub Arnold
Answered By : nneonneo
Simply compute the index of the permutation into the sorted list of all permutations and use that as your hash key. This can be achieved with a relatively simple algorithm: http://stackoverflow.com/questions/5131497/find-the-index-of-a-given-permutation-in-the-sorted-list-of-the-permutations-of Once you have that index, you can make a table with exactly 9! slots – you have a perfect hash over your input domain. For example, for n=3, the hash function produces
123 -> 0 132 -> 1 213 -> 2 231 -> 3 312 -> 4 321 -> 5
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/39625
