作者tropical72 (藍影)
站內Prob_Solve
標題[問題] 中介數編解碼
時間Mon Feb 6 03:52:36 2012
下述說明, array index start from 0.
不知道這有沒有明確定義的名詞 < 其實是在排列演算法裡面看到的 >。
現假設一 arr[] = {6,3,4,5,1,2};
中介數 n[i] 代表 arr[i] > arr[j] ( for j>i) 之個數，
白話點，就是元素 a[i] 以右，比 a[i] 還大的個數。
以 n[1] 為例，arr[1] 右邊比 arr[1] 大的數有 2 個， n[1]=2；
n[2] ,arr[2] arr[2] 1 , n[2]=1。
----
這裡做幾個前提假設
a. 假設 array 數值分佈為 [1,n] 或 [0,n-1]
b. 每個數都剛好會出現一次。
問題有三個
1. 有辦法快速知道 n[] 值嗎？ (可接受額外空間)
目前作法是
for(i=0; i<size; ++i)
for(n[i]=0, j=i+1; j<size; ++j)
n[i]+=(arr[j]>arr[i]);
因這動作非常頻繁，不知是否有其他作法？
2. 怎麼再解碼回去？ (可接受額外空間)
若 n[] = {1,0,2,1 } ; 我該怎麼解碼解成
arr[] = {4,5,3,1,2} 或 {3,4,2,0,1}？
const int size=5;
char used[size]={0};
int i, j, cnt;
for(i=0; i<size-1; ++i){
cnt = 0;
for(j=size-1; cnt!=n[i]; --j)
if(used[j]==0) ++cnt;
arr[i] = j, used[j]=1;
}
// 最後還要查一次沒用到的
for(i=0; i<size && used[i]; ++i) ;
arr[size-1] = i;
目前想法也是豬頭想法，只差無限猴子定理沒搬出來做，
不知能否有些技巧？
3. 假設不成立時，中介數之編解碼是否該重新設計？
倘若 假設 a. array 數值分佈為 [1,n] 或 [0,n-1] 不成立，
唯一確定的是 array 元素保證兩兩相異，試問還有什麼技巧可完成？
----
這篇發得很像作業文，但純粹是個人進修卡住，
希望各位先進能不吝給個意見。
懇請不吝賜教，小弟感激不盡。
--
世界上有種，
將 不可能 轉換為 無限可能 的強大力量，
我稱它為 - 信念。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.165.40
1F：→ fatcats:n[2] = 1 02/06 03:58
2F：→ fatcats:因為你寫 元素 a[i] 以右，比 a[i] 還大的個數@@" 02/06 03:59
3F：→ tropical72:嗯嗯,前半段筆誤之處已修正,謝謝 f 大. 02/06 04:02
補上目前使用的程式碼。
※ 編輯: tropical72 來自: 123.195.165.40 (02/06 04:09)
4F：→ firejox:這種東西就是逆序數阿... 02/06 22:59
5F：→ firejox:逆序數的作法有很多 就我目前所知可以用樹狀數組、合併排 02/06 23:02
6F：→ firejox:還有快排(stable)處理 02/06 23:02
7F：→ tropical72:謝謝 f 大提供 keyword ^^ 02/06 23:06
8F：→ firejox:有一種方法叫離散化就可以使整體資料化為1~n或0~n-1之間 02/06 23:08
9F：→ firejox:如果有重複的資料 在編解碼上會更困難 02/06 23:09
10F：→ tropical72:離散化指的應就是我於程式碼中 char used[] 之意？ 02/06 23:13
11F：→ firejox:不是 離散化可以應用在算逆序數的層面 02/06 23:17
12F：→ firejox:就是把一群過於離散的資料適當的規類 02/06 23:26
13F：→ firejox:還有一點就是 以內容為基準的編碼還是以位置為編碼... 02/06 23:30
14F：→ tropical72:內容或位置之編碼？有差嗎？到時都還要再解碼回來~ 02/07 00:12