What would be the most space-efficient way to represent a multiset (a set that can contain duplicates) using a (static) bit string (bit vector, bit array, etc.)? All of the elements in the multiset would be integers from a limited range.
My current approach is to find the greatest frequency and allocate that number of bits to each element (i.e the multiset [0,1,1,2,3,3,3,3,4] becomes 1000 1100 1000 1111 1000), but this is rather inefficient.
For reference, the larger problem is that I want to securely calculate the intersection between two multisets, so I pretty much need each bit to correspond to an element. I also need two parties to be able to build a bit string where each bit corresponds to the same element without giving away much information in the process.