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

看板C_and_CPP作者 (牛牛)時間10年前發表 (2014/10/21 08:57), 10年前編輯推噓13(13033)
留言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
如果只有1跟0我只想到轉成10進制記下總和 再回推回去
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
Prob_Solve 或者 Programming 這兩個版可以問看看
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
我以前曾經寫一個程式是加一個 index,排序時只排
10/21 20:46, 9F

10/21 20:47, , 10F
index 的陣列,沒有動到原始的資料,這樣同樣的資料
10/21 20:47, 10F

10/21 20:47, , 11F
可以做好幾種排序,只要加一個 index 就有一種排序。
10/21 20:47, 11F

10/21 20:48, , 12F
只是好像與原 po 的需求不太符合,sorry,胡言亂語。
10/21 20:48, 12F

10/21 20:52, , 13F
有多種原始資料可以得到妳的排序資料 要回到哪一種?
10/21 20:52, 13F

10/21 20:54, , 14F
有 10! 種輸入排好後會變成 1 2 3 4 5 6 7 8 9 10
10/21 20:54, 14F

10/21 21:24, , 15F
我想原po大概是很單純的想做 stack rollback 動作而已吧
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
這動作就是我上面說的 stack rollback (不知道正不正式.)
10/21 22:12, 17F

10/21 22:33, , 18F
真的要記用樓上的方法應該是最省memory的
10/21 22:33, 18F

10/21 22:34, , 19F
P.S 排好的不需要存 記0跟1的數量就好
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
小於 2n 是怎樣的概念? 那 2n - 1 呢 ?
10/21 23:33, 22F

10/21 23:34, , 23F
有1*n個序列,原圖加排序後,不是(1*n)*2=2*n嗎?
10/21 23:34, 23F

10/21 23:35, , 24F
2^n是等比級數膨脹的吧
10/21 23:35, 24F
我想說 排序的序列我要拿來用 應該是n才對 我想錯 好丟臉= =" ※ 編輯: angelina877 (111.254.246.253), 10/21/2014 23:41:36

10/22 00:01, , 25F
紀錄大小 < n 我覺得不太可能 , 扣除計數式排序 , 最快
10/22 00:01, 25F

10/22 00:02, , 26F
是 O(n logn) , 若每次紀錄的是交換的兩個索引 (i,j),
10/22 00:02, 26F

10/22 00:03, , 27F
那大小估算大概也要 2 * n * log(n)
10/22 00:03, 27F

10/22 00:05, , 28F
等等... 插入排序應該只要 2*n 就行了...
10/22 00:05, 28F

10/22 00:05, , 29F
講錯,是交換排序 Orz , 插入排序還沒想空間需求
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
我是有想到可以省1,2bits的方法,不過很鳥~~~
10/22 01:54, 32F

10/22 01:56, , 33F
例如a[0,0,1,1,1,1,0,1] b[0,0,1,1,1,1,0] 少的bit
10/22 01:56, 33F

10/22 01:56, , 34F
就補1,這樣可以偷工減料少記錄1bit
10/22 01:56, 34F

10/22 01:57, , 35F
如果運氣好 a[0,0,1,1,0,0,1,1],則b[0,0,1,1,0,0]
10/22 01:57, 35F

10/22 01:57, , 36F
則可以偷工減料2bits XD 運氣不好就.......
10/22 01:57, 36F

10/22 05:05, , 37F
總覺得這樣就不要動原始資料,只要分別記 0, 1 的個數
10/22 05:05, 37F

10/22 05:06, , 38F
就是排序的結果了。這樣算花 2*log n bits 嗎?
10/22 05:06, 38F

10/22 05:27, , 39F
a[0,0,1,1,1,1,0,1] b[0,0,0],話說這樣根本就連排
10/22 05:27, 39F

10/22 05:28, , 40F
序都不用了,直接算0的個數就是結果@@
10/22 05:28, 40F

10/22 07:33, , 41F
怎麼聽起來比較像數數+壓縮阿
10/22 07:33, 41F

10/22 07:33, , 42F
把一堆壓縮演算法都拿來試試看阿XD
10/22 07:33, 42F

10/22 09:05, , 43F
popcount?
10/22 09:05, 43F

10/22 10:31, , 44F
那就原序列不要動, 只算總共幾個 0 or 1 最多用 4bits
10/22 10:31, 44F

10/22 10:32, , 45F
不過原序列都用掉 8bits 了, 省這幾 bits 讓人費解 R
10/22 10:32, 45F

10/22 10:37, , 46F
甚至也可以根本就不存, 要用到排序數列時再算出來就好了
10/22 10:37, 46F
文章代碼(AID): #1KHY0CK2 (C_and_CPP)
討論串 (同標題文章)
文章代碼(AID): #1KHY0CK2 (C_and_CPP)