Re: [問題] 排序演算法 可逆式
看來還是回文比較清楚，拋磚引玉。
※ 引述《angelina877 (牛牛)》之銘言：
: 問題(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
我重提一下最原始的前提，
(1) 資料只有 0/1
(2) 一開始是知道未排序的陣列(A) ， 經過一連列動作(S) 後得到 (B) ,
現在要再由 B 回到 A
: 有人說 直接把原圖記起來 是個好方法 但是紀錄大小就是 n(更正)
↑ 這句話我認為不需要知道排序過程，所以下面這方向應該是可參考的。
前提只有上述，但在空間分析上沒定義清楚，
陣列裡的元素是用 sizeof(int)==4 , sizeof(char)==1 , 還是 1 bits 計算
我以 1 bit 方式做計算。
另外要講，這前提其實有很多方法可以達到
[Method 1]
其實只要多一個陣列，紀錄原本 1 的位置就行了，
以 int ary[] = {1,1,0,1,1,0,0 };
vector<int> pos{0,1,3,4};
到時候還原沒紀錄到的就是 0 ，
而 size 我們可以從排序的陣列 {0,0,0,1,1,1,1} 知道陣列大小是 7 。
所需空間大很多，其它不多說。
[Method 2]
資料量不大的話其實很好做，拿原始舉例說的
1101100 --> 0001111
用 2 進位看這串資料，轉成 10 進位會是
108 --> 15 ， double d = 108 / 15 = 7.2
再將 15 換回 108 怎辦？沒錯，用簡單的乘除法就行了，乘回去
15 * (d=7.2) = 108
上面模型是 y = ax , 其中 a 為浮點數。
這方法第一個會遇到的問題是可能會有浮點數誤差，而且機會蠻大的，但其實不難解，
就是將模型改成 y = ax + b, 其中 a, b 都改成整數就行了。
108 ---> 15 ， int a = 108 / 15 = 7
int b = 108 - 15 * 7 = 3
轉回來時變成 15 * 7 + (+3) = 108 ，這就去掉了浮點數誤差問題。
換句話說，只要元素個數在 64 個以內，它就只需要額外 2 個整數就能算完了。
第二個會遇到的問題是，這方法在現有 compiler POD 情形下，只能解64個元素之陣列，
但更廣義的說，這也是大數算法的一種變形，去載個 gmp lib 應可用得很開心。
而且這裡從頭到尾可用 2^n 進位大數算法做 (完全不用轉到 10 進位)，
應該很省空間才對。
針對第二個 issue , 有更好的做法嗎？答案是有的！！
提示是，當超過了 64 bits 之後，上面的 a, b 就會變成了 array。
但 32 / 64 bits 太長了，我假設 int 最大只能存 4 bits , 資料假設如下
y = ax + b
y 原始資料 : 0000 1110 1010 0000
↓ ↓ ↓ ↓
x 排序資料 : 0000 0000 0001 1111
a : 0 0 10 0
b : 0 12 0 0
所以當 a==b==0 的時候，唯一的情況是原始資料是 0，其他的一定都可以推出來。
這種方式，如果一個元素是用 1 bit 計算的話，若有 n bits ( n/8 bytes)
所需額外空間約是 n/32 * 8 bytes = n / 4 bytes，原本空間的 2 倍。
再縮小的話，就用 xor 了
y 原始資料 : 0000 1110 1010 0000
↓ ↓ ↓ ↓
x 排序資料 : 0000 0000 0001 1111
z (xor) : 0000 1111 1011 1111
拿到 x 之後，再對 z 做 xor ，這樣就能回到 y 了，
所需空間和原本一樣 (又沒進步了 Orz )
[Method 3]
stack rollback 動作，這個我不想再說了，有興趣的人應該都可以實作出來。
但空間需求會比上面的方法較大，原因是這特例嚴謹的話可用 1 bit 存空間。
--
~ 這輩子與神手無緣
我只好當神獸了 ~
卡卡獸
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.74.8
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1413911802.A.699.html
推
10/22 01:34, , 1F
10/22 01:34, 1F
唉，搞了半天想了個方法還是壓不下原本的空間。
※ 編輯: EdisonX (180.177.74.8), 10/22/2014 01:51:36
推
10/22 02:14, , 2F
10/22 02:14, 2F
→
10/22 02:16, , 3F
10/22 02:16, 3F
討論串 (同標題文章)