[問題] 中介數編解碼

[tropical72 (藍影)]

下述說明, 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
→ fatcats:n[2] = 1
→ fatcats:因為你寫 元素 a[i] 以右，比 a[i] 還大的個數@@"
→ tropical72:嗯嗯,前半段筆誤之處已修正,謝謝 f 大.
補上目前使用的程式碼。
※ 編輯: tropical72      來自: 123.195.165.40       (02/06 04:09)
→ firejox:這種東西就是逆序數阿...
→ firejox:逆序數的作法有很多 就我目前所知可以用樹狀數組、合併排
→ firejox:還有快排(stable)處理
→ tropical72:謝謝 f 大提供 keyword ^^
→ firejox:有一種方法叫離散化就可以使整體資料化為1~n或0~n-1之間
→ firejox:如果有重複的資料 在編解碼上會更困難
→ tropical72:離散化指的應就是我於程式碼中 char used[] 之意？
→ firejox:不是 離散化可以應用在算逆序數的層面
→ firejox:就是把一群過於離散的資料適當的規類
→ firejox:還有一點就是 以內容為基準的編碼還是以位置為編碼...
→ tropical72:內容或位置之編碼？有差嗎？到時都還要再解碼回來~