作者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