推 cutekid: 推唷(Y)，以 n = 8 來講,只須用 4 ~ 7 bits 即可 10/22 10:36
推 wowslr: 推此篇 XD 10/22 11:10
推 DJWS: n個數字重新排列有n!種可能 01序列重新排列有C(n,n/2)種可能 10/22 15:24
→ DJWS: 應該不是 2^n-1 吧 10/22 15:24
→ cutekid: 因為原提問者的數據只會有 0 or 1 兩種數字 10/22 16:12
→ cutekid: 所以「原始序列」會有 2^n - 1 種可能 10/22 16:15
推 angelina877: 其實看懂一半 我用的理解說說看 10/22 21:31
→ angelina877: 假設有[0 0..n個..0 1 1...m個 1] 10/22 21:32
→ angelina877: 總共會有(n+m)!/n!m!個bit<n+mbit這樣嗎 10/22 21:34
→ angelina877: 但是有一個疑惑 如果n跟m很大(ex:2000) 那階層不就 10/22 21:36
→ angelina877: 非常大嗎 10/22 21:36
→ LPH66: 不是 C(n,m) bits 而是 log_2 C(n,m) bits 10/22 21:53
→ LPH66: 而 C(n,m)≦C(n,n/2)≒O(2^n/√n) (Catalan number appox.) 10/22 21:55
→ LPH66: [啊, 寫到這裡才發現我的 n 是總長度...] 10/22 21:56
→ LPH66: 取 log_2 確實是比 n 稍小一些些 10/22 21:56
→ kevingwn: 不然最簡單的作法就是只紀錄原始序列的n-1 bits 10/23 02:09
→ kevingwn: 剩下那個bit用排序序列去推是0或1,這樣也能達成你的需求 10/23 02:10
→ kevingwn: 再看了一下果然寫錯了,原始序列是2^n種可能啦 10/23 02:19
推 DJWS: 我 typo 了 應該是 angelina877 說的 (n+m)!/n!m! 才對 10/23 07:49
→ DJWS: 然後其實我想的也是錯的 應該是樓上說的 2^n 才對 10/23 07:52