I have permutations:
4 1 2 5 3
4 3 2 5 1
numbers can be order magnitude of 1000 (fits in two bytes) I want compute 32 bit (or better 64 bit) hashes, it should be non cryptographically secure but evenly distributed in 32 or 64 bits.
This second permutations is derived from first by swap 1-st and 4-th element (count form zero). I want incremental hash: if I know hash of first permutation, should be fast and easy obtain hash of second by knowing only 1-st and 4-th element.
Apart from evenly distribution, candidate can be modified XOR. XOR has disadvantage, that is insensitive to order - modified XOR computes xor with numbers and its positions. Smaller disadvantage , that would be 10-12 bits for this numbers instead of 32 or 64 bits, but 10-12 bits is enough to unique distinguish between permutations? when number bits would be order of magnitude of log2(permutation len)?
Unfortunately xor of permutation give 0 (or constant number?), xor of two permutations also.. Is possible add bit rotations but with incrementality?
What about checksum defined below: simple sum is insensitive to order, but if we sum products: tab[index]*(index+1)? This is order sensitive.