I'm looking for a method of storing data within the order of a dictionary when it is being transmitted. As the order of a dictionary doesn't matter, it provides an ideal place to store data that is likely to be overlooked.
For the purposes of this, the fact it's a dictionary doesn't matter, so I'll model it as a list.
I have a list of size 3 with values A, B, C and D.
The ideal amount of data I can store in this is log2(n!) where n=4 with is 4.58... so 4 bits.
There are a number of simple methods that approach n-1 bits that can be stored, for example a simple method for n-1 efficiency:
I have the same list as above, A..D.
I start with the first element
I place the next elements before or after it - each referring to a 1 or a 0.
For example:
000 -> DCBA
001 -> CBAD
010 -> DBAC
100 -> BACD
There are a few optimisations on this that would provide a few extra percent of bits stored, but I'd like to know (if possible) if there is a method that would approach the theoretical maximum, or at least provide a significant boost to the efficiency of this method.
For some more context, I am looking to store data in the order of HTTP request header fields.
I'm looking for an algorithm, not a piece of code, if possible.
I figured this out by using a quicksort style algorithm, however instead of comparing each element to the pivot, the next bit from the 'Datasource' is used. As I'm answering my own question and there has been very little interest in this question, I'm not going into huge detail, but am happy to do so if asked.