Saturday, May 12, 2018

[dmpvhcjz] Storing a permutation

Consider a storing a permutation of 2^8 = 256 elements.  The easiest way to store it is a byte array of length 256, consuming 8*256 = 2048 bits total.

The densest possible encoding is mixed radix based on the factorial, requiring log(256!)/log(2) = 1683.996 bits.  (The .996 is a nice coincidence.)

A hybrid approach does bit-packing.  The first 128 elements use 8 bits per element, then the next 64 use 7 bits, and so forth.  sum(i=0,7,2^i*(i+1)) = 1793 bits.

No comments :