Hashing the arrangement of an array

user_402169 0
Viewed 274

I am trying to write a function which takes an array of integers, and outputs a hash value to signify their arrangement order. The hash key should be as small as possible (we're dealing with embedded and space/execution optimization is critical)

template<size_t N>
int CalculateHashOfSortOrder(int* itemsBegin)
{
    // return ???
}

In other words, an array [ 4, 2, 1, 3 ] should produce an ID which reflects their order and would match any of the following arrays:

[ 4, 2, 1, 3 ]
[ 4, 2, 0, 3 ]
[ 400, 200, 100, 300]
et al

I am at a loss for how to do this in the most efficient way possible. What is the algorithm to approach this? The methods I come up with seem extremely slow.

For example, given the above example, there are 24 possibly arrangements (4 * 3 * 2 * 1), which would fit into 5 bits. Those bits can be calculated like this:

  • 1st value (1). There are 4 positions possible, so 2 bits are needed to describe its position. This value is at position 2 (0-based). So push binary 10.
  • 2nd value (2). There are 3 positions possible, so 2 bits are needed. It's at position 1, so push binary 01. Hash key is now 1001b.
  • 3rd value (3). There are 2 positions possible, so 1 bit is needed. It's at position 1 of the remaining values, so push 1.

The resulting key is 10011b, but I don't see a clear way to make that anything but obnoxiously inefficient. I think there's another way to approach this problem I just haven't thought of.

edit: A couple ideas come to mind:

  1. Calculate the rank of each item in the array, and hash the rank array. Then by what method can you pack that rank array into a theoretically-smallest ID? This appears to be the most vexing element of my question.
  2. Find a way to save item rank as they're inserted, optimizing #1
  3. For sufficiently small # of items (<10), it may be possible to just generate a huge tree of if() statements via metaprogramming. Need to see if exe size would be a problem.
optimization algorithm c++
4 Answers

An equivalent hash goes something like this for [ 40, 20, 10, 30 ]

  1. 40 is greater than 3 of the subsequent values
  2. 20 is greater than 1 of the subsequent values
  3. 10 is greater than 0 of the subsequent values
  4. 30 has nothing after it, so ignore it.

That is a pair nested loop of time Order(N^2). (Actually about 4*4/2, where there are 4 items.) Just a few lines of code.

Pack 3,1,0, either the way you did it or with anatolyg's slightly tighter:

3 * 3! +
1 * 2! +
0 * 1!

which equal 20. It needs to be stored in the number of bits needed for 4!, namely 5 bits.

I'm pretty sure this is optimal for space. I have not thought of a faster way to compute it other than O(N^2).

How big is your N? For N=100, you need about 520 bits and 5K operations. 5K operations might take several microseconds (for C++), and probably less than a millisecond (even for an interpreted language).

user_17668310

Use something like factorial number system. If you concatenate bits, it's as if you multiply the first number by some power of 2, the second number by another power of 2, etc. In factorial number system, you multiply by a more "fair" factor, which is not a power of 2.

To make the result small, calculate it modulo some small prime number, e.g. 127. Or a moderately big prime number. The "mod" actually should not necessarily be a prime number, it just shouldn't have any prime factors smaller than N (the length of your list).

user_5098680

To calculate the rank of each item in the array

  • sort two arrays in parallel (or an array of 2-tuples, if your language makes that easy). The first element in the array is the value, the second is the initial index. Keep in mind that you can use radix sort, if these are really integers.
  • At the end, drop the sorted values, and only look at the indices. This is the array of ranks (well actually, it's the inverse permutation of the array of ranks, but since you're hashing I assume you don't care).

Then, convert the array of ranks into bits. You can look at how to store a "permutation" or use factorials, if you really want to pack it in. Or, you can just use (log n) bits per number, and pack them all together--as long as you don't need to reverse this whole process, that's what I'd recommend. You need about N log(N) bits regardless of how you do this, but you can get that multiplier down to the minimum in practice if you need.

The metaprogramming technique you describe is called a "sorting network", and is used to make sorts much faster when you get down to the smallest groups at the end of recursive sorts.

Can you say more about your actual problem? This sounds likely to be a XY problem.

user_3918960
user_20410770
Related