如何對集合中的數據進行壓縮？

01-01

假設有16種不同元素，那麼我們需要用4bit表示一個元素。
再假設我們的集合中固定有4種不同的元素，那麼將這四個元素拼接起來就可以表示這個集合，共需要16bit。
然而一個集合中的數據並沒有順序關係，因此會有24種不同的組合表示同一個集合，理論上講應該可以只使用12bit就表示這樣一個集合。
不知道都有什麼演算法能夠將這16bit壓縮至12bit？最好是通過這4個4bit元素之間的運算來得到這12bit，而不是硬生生的將各種可能的集合編號然後查表……
Milo Yip大神提供的方法簡單來說就是先對集合中的元素排序，保證每個同一個集合只有一種表示，然後再對這種表示排序編號，緊湊地表示了集合。這種方式很有效，但是需要計算大量的組合數，可能不太適用於我的項目，不知道還有沒有大神了解其他巧妙的方法，稍微有一兩bit冗餘也可以，只要比原本那種表示方式少就行

如果更具體些，這些元素本身是一個伽羅華域的元素，也就是說全集構成了一個群，那麼有沒有什麼性質可以利用來壓縮這個集合呢？如果能在不解碼的情況下簡單判斷一個元素是否屬於一個集合那就更好了（雖然我覺得這個要求不是很現實…）

由於 $C^{16}_4 = 1820 < 2^{11}$ ，可以知道只需要11 bit就能存儲選取自16個元素的4元素集合。

標準編碼方法應該是 Combinatorial number system。找到一篇相關的文章 A maximally-dense encoding for n-choose-k 可供參考。

普遍的做法就是離散化

4重循環+排序

用的時候2分查找

如果想省掉集合內4元素的排序

直接按序號0-15 S=2^i+2^j+2^m+2^n

上次的答案很果斷的錯了。。。看了看這麼多天沒新的答案，我把這次這個還是寫出來吧。。

先原文:

0000 1110 0010 0110

1.16bit四組，進行排序,使最後一位較多的(這次是0)盡量靠後

0000 0010 0110 1110

2.取每組數最後一位，倒數第二位.......形成新的四組數

0000 0111 0011 0001

併合並為16數

0000011100110001

3.開頭的相同數字刪除

11100110001

結果為11bit

最優情況

1111 0111 0011 1011

1111 0111 1011 0011

1111 1111 1100 1010

001010

--6bit

最次情況

1010 0101 1001 0110

1010 0110 1001 0101

0011 1100 0101 1010

11110001011010

--14bit

解碼:

11100110001

0000011100110001

0000 0111 0011 0001

0000 0010 0110 1110

沒臉見人惹。