[問題] 排序演算法 可逆式
看板C_and_CPP作者angelina877 (牛牛)時間10年前發表 (2014/10/21 08:57), 10年前編輯推噓13(13推 0噓 33→)留言46則, 16人參與討論串1/6 (看更多)
問題(Question):
我們都學過很多排序演算法,
如Bubble Sort,Merge Sort,Insert Sort
今天,小妹有一個問題
就是如何在已經排好的數列中,去回復原始資料,
請問有這種演算法嗎? 我找了一段時間 沒找到
EX
原始資料
[1,1,0,1,1,0,0]
1.使用演算法 得到排序資料
[0,0,0,1,1,1,1]
2.再從排序資料中回復成原始資料
[1,1,0,1,1,0,0]
補充說明(Supplement):
我找了好多天了,實在是挫折連連
逼不得已才上來問QAQ
希望高手相救XDD
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.254.246.253
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1413881868.A.502.html
→
10/21 17:13, , 1F
10/21 17:13, 1F
推
10/21 17:33, , 2F
10/21 17:33, 2F
→
10/21 17:34, , 3F
10/21 17:34, 3F
→
10/21 17:35, , 4F
10/21 17:35, 4F
http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
目前唯一找到比較相近的 但是還有一點問題就是了
知道通常不會 但是 就是需要 所以才發問咩XDD
※ 編輯: angelina877 (111.254.246.253), 10/21/2014 17:42:46
推
10/21 17:48, , 5F
10/21 17:48, 5F
推
10/21 18:04, , 6F
10/21 18:04, 6F
推
10/21 18:56, , 7F
10/21 18:56, 7F
→
10/21 19:34, , 8F
10/21 19:34, 8F
簡單來說 就是需要咩....
我只是把自己的問題 拆成一個小問題來問
真正要說為什麼 就是我要再排序數列做處理
講起來很複雜 就省略解釋了
所以 有人知道嗎 冏
※ 編輯: angelina877 (111.254.246.253), 10/21/2014 20:37:17
推
10/21 20:46, , 9F
10/21 20:46, 9F
→
10/21 20:47, , 10F
10/21 20:47, 10F
→
10/21 20:47, , 11F
10/21 20:47, 11F
→
10/21 20:48, , 12F
10/21 20:48, 12F
→
10/21 20:52, , 13F
10/21 20:52, 13F
→
10/21 20:54, , 14F
10/21 20:54, 14F
→
10/21 21:24, , 15F
10/21 21:24, 15F
可能是表達能力 問題沒講清楚
我再試試看 換一種方式表達
有一個1*n的序列or矩陣
原始序列 只有1跟0,兩個變數隨機排列
[0 0 1 1 1 1 0 1]
我要的演算法是
1.將原始序列作有序排序(0<1)
所有的0都在前面,所有的1都在後面
[0 0 0 1 1 1 1 1]
2.將排序序列 做返可逆
[0 0 1 1 1 1 0 1]
ps.可逆的0是第幾個0,第幾個1無所謂,只要排序方式相同就好
※ 編輯: angelina877 (111.254.246.253), 10/21/2014 22:03:37
→
10/21 22:11, , 16F
10/21 22:11, 16F
→
10/21 22:12, , 17F
10/21 22:12, 17F
推
10/21 22:33, , 18F
10/21 22:33, 18F
→
10/21 22:34, , 19F
10/21 22:34, 19F
→
10/21 23:08, , 20F
10/21 23:08, 20F
→
10/21 23:09, , 21F
10/21 23:09, 21F
果然 問到一個很難的技術
或者條件太高
可以記錄 但是紀錄的條件是
有1*n個序列 那紀錄大小必須<n(更正)
有人說 直接把原圖記起來 是個好方法 但是紀錄大小就是 n(更正)
btw 想出來的 小妹願意從打工的錢裡面 拿出NT500 犒賞一下XD
※ 編輯: angelina877 (111.254.246.253), 10/21/2014 23:15:22
→
10/21 23:33, , 22F
10/21 23:33, 22F
推
10/21 23:34, , 23F
10/21 23:34, 23F
→
10/21 23:35, , 24F
10/21 23:35, 24F
我想說 排序的序列我要拿來用 應該是n才對 我想錯 好丟臉= ="
※ 編輯: angelina877 (111.254.246.253), 10/21/2014 23:41:36
→
10/22 00:01, , 25F
10/22 00:01, 25F
→
10/22 00:02, , 26F
10/22 00:02, 26F
→
10/22 00:03, , 27F
10/22 00:03, 27F
推
10/22 00:05, , 28F
10/22 00:05, 28F
→
10/22 00:05, , 29F
10/22 00:05, 29F
→
10/22 00:37, , 30F
10/22 00:37, 30F
→
10/22 00:42, , 31F
10/22 00:42, 31F
拍謝 讓大家費神想那麼多 真是感動
我應該掌我自己嘴的 問問題也不講清楚
如果是以座標來記得話
[0 0 1 1 1 1 0 1]
^
第(1,3)的1 應該第一列可以省下來 看第3行應該算紀錄成 010 3bit
我的想法是這樣
所以 記錄值<8bit 是要求
ps.微薄獎金,不強迫每個人參加
如果真的想不出來
我就樂捐慈善單位
※ 編輯: angelina877 (111.254.246.253), 10/22/2014 01:53:14
推
10/22 01:54, , 32F
10/22 01:54, 32F
→
10/22 01:56, , 33F
10/22 01:56, 33F
→
10/22 01:56, , 34F
10/22 01:56, 34F
→
10/22 01:57, , 35F
10/22 01:57, 35F
→
10/22 01:57, , 36F
10/22 01:57, 36F
→
10/22 05:05, , 37F
10/22 05:05, 37F
→
10/22 05:06, , 38F
10/22 05:06, 38F
推
10/22 05:27, , 39F
10/22 05:27, 39F
→
10/22 05:28, , 40F
10/22 05:28, 40F
推
10/22 07:33, , 41F
10/22 07:33, 41F
→
10/22 07:33, , 42F
10/22 07:33, 42F
推
10/22 09:05, , 43F
10/22 09:05, 43F
推
10/22 10:31, , 44F
10/22 10:31, 44F
→
10/22 10:32, , 45F
10/22 10:32, 45F
→
10/22 10:37, , 46F
10/22 10:37, 46F
討論串 (同標題文章)