Re: [問題] 排序演算法 可逆式

看板C_and_CPP作者 (如雲如風的人生)時間9年前 (2014/10/22 09:50), 編輯推噓5(5推 0噓 15→)
留言20則, 6人參與, 最新討論串6/6 (看更多)
你需要的是 可以將排序序列展開所有可能的演算法 然後紀錄下原始序列是第x種展開就好 因為排序序列展開一定少於原始序列(2^n-1) 所以這個x值一定可以用少於n bits紀錄 這樣就達成你的需求了 至於從排序序列展開的演算法就自己想吧 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.129.19 ※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1413942649.A.5D7.html
推
10/22 10:36, , 1F
推唷(Y)，以 n = 8 來講,只須用 4 ~ 7 bits 即可
10/22 10:36, 1F
推
10/22 11:10, , 2F
推此篇 XD
10/22 11:10, 2F
推
10/22 15:24, , 3F
n個數字重新排列有n!種可能 01序列重新排列有C(n,n/2)種可能
10/22 15:24, 3F
→
10/22 15:24, , 4F
應該不是 2^n-1 吧
10/22 15:24, 4F
→
10/22 16:12, , 5F
因為原提問者的數據只會有 0 or 1 兩種數字
10/22 16:12, 5F
→
10/22 16:15, , 6F
所以「原始序列」會有 2^n - 1 種可能
10/22 16:15, 6F
推
10/22 21:31, , 7F
其實看懂一半 我用的理解說說看
10/22 21:31, 7F
→
10/22 21:32, , 8F
假設有[0 0..n個..0 1 1...m個 1]
10/22 21:32, 8F
→
10/22 21:34, , 9F
總共會有(n+m)!/n!m!個bit<n+mbit這樣嗎
10/22 21:34, 9F
→
10/22 21:36, , 10F
但是有一個疑惑 如果n跟m很大(ex:2000) 那階層不就
10/22 21:36, 10F
→
10/22 21:36, , 11F
非常大嗎
10/22 21:36, 11F
→
10/22 21:53, , 12F
不是 C(n,m) bits 而是 log_2 C(n,m) bits
10/22 21:53, 12F
→
10/22 21:55, , 13F
而 C(n,m)≦C(n,n/2)≒O(2^n/√n) (Catalan number appox.)
10/22 21:55, 13F
→
10/22 21:56, , 14F
[啊, 寫到這裡才發現我的 n 是總長度...]
10/22 21:56, 14F
→
10/22 21:56, , 15F
取 log_2 確實是比 n 稍小一些些
10/22 21:56, 15F
→
10/23 02:09, , 16F
不然最簡單的作法就是只紀錄原始序列的n-1 bits
10/23 02:09, 16F
→
10/23 02:10, , 17F
剩下那個bit用排序序列去推是0或1,這樣也能達成你的需求
10/23 02:10, 17F
→
10/23 02:19, , 18F
再看了一下果然寫錯了,原始序列是2^n種可能啦
10/23 02:19, 18F
推
10/23 07:49, , 19F
我 typo 了 應該是 angelina877 說的 (n+m)!/n!m! 才對
10/23 07:49, 19F
→
10/23 07:52, , 20F
然後其實我想的也是錯的 應該是樓上說的 2^n 才對
10/23 07:52, 20F
‣ 更多 kevingwn 的文章
文章代碼(AID): #1KHmrvNN (C_and_CPP)
‣ 更多 kevingwn 的文章
文章代碼(AID): #1KHmrvNN (C_and_CPP)