一個(gè)數(shù)字變換的惟一性問題

woodie

問題的緣起是技安網(wǎng)友提的一個(gè)問題，大意是一個(gè)文件中的每行有3個(gè)十進(jìn)數(shù)字，相同的組合但順序不同視為重復(fù)，只保留其中一種組合，其余不同排列方式的行刪除。這個(gè)帖子有許多網(wǎng)友參加討論并且當(dāng)時(shí)已經(jīng)認(rèn)為被解決了，實(shí)際上其中一種用awk的解法是有些遺漏的。最近技安網(wǎng)友發(fā)現(xiàn)了這個(gè)問題并再次發(fā)貼求助，很遺憾由于相互產(chǎn)生了一些誤解，搞得有些不愉快。其實(shí)大可不必，上論壇是來交流的，又不是斗氣的，大家最好就事論事。就算錯(cuò)了也沒什么大不了，小弟我就經(jīng)常犯錯(cuò)——不好意思，有些還是低級(jí)錯(cuò)誤，所以臉皮也混得越來越厚了。竊以為能承認(rèn)錯(cuò)誤是有肚量、有風(fēng)度的體現(xiàn)。怎么樣我臉皮夠厚吧，這不是繞著彎表揚(yáng)自己嘛？嘿嘿^_^。其實(shí)人非圣賢，孰能無過？大家哈哈一笑揭過算了，千萬別傷了和氣。

參考帖：
1.技安兄首次提問
2.技安兄二次提問

玩笑開過了，咱們言歸正傳。

用awk解決類似問題的思路一般是使用所謂的“關(guān)聯(lián)數(shù)組”，實(shí)際上就是hash表，鍵是數(shù)組下標(biāo)，值就是數(shù)組的值。程序大致上是這樣：

1. awk '!array[key]++'

復(fù)制代碼

這等價(jià)于

1. awk '!array[key]++{print $0}'

復(fù)制代碼

當(dāng)key對(duì)應(yīng)的值不存在時(shí)設(shè)置這個(gè)鍵值(++操作使該數(shù)組元素由0變?yōu)?)，并打印當(dāng)前行；當(dāng)對(duì)應(yīng)的鍵值存在時(shí)表示已經(jīng)有相應(yīng)的記錄存在，則不打印當(dāng)前行。這就保證了鍵值惟一時(shí)對(duì)應(yīng)輸出行的惟一。

于是用awk解決這個(gè)問題的關(guān)鍵就是如何構(gòu)造hash鍵的問題了。即是將文件中所有行變換到一個(gè)鍵的集合，對(duì)于這個(gè)問題，不同數(shù)字的組合得到的鍵應(yīng)當(dāng)不同；反之就可能遺漏掉一些有效的組合。那么如何構(gòu)造呢？不同的人可能有不同的方法，但只要能證明變換的惟一性就行了，窮舉法證明也行。

我的思路是：首先將變換分為兩部分，單個(gè)數(shù)字的變換(簡(jiǎn)記為變換1)和3個(gè)數(shù)字綜合的變換（簡(jiǎn)記為變換2）。
1.由于幾個(gè)數(shù)字的順序是不重要的，類比數(shù)學(xué)中的運(yùn)算加法和乘法都滿足交換率，所以各個(gè)加數(shù)和因子的順序也是不重要的。所以變換2可以采用加法或乘法運(yùn)算，將每一個(gè)數(shù)字的變換結(jié)果連結(jié)起來，如此就可以滿足順序無關(guān)的條件。
2.那如何選擇變換1的形式，并且保證最終變換的惟一性呢？我想到兩個(gè)方法：
a.一個(gè)是變換2使用加法運(yùn)算的，我在參考貼2的8樓已經(jīng)給出了一種形式：
就是將每個(gè)數(shù)字后面加上若干個(gè)0,即0變成0，1變成10,2變成200,3變成3000,...依此類推，9變成9x10^9。
f(n)=n*10^n
這樣可以保證同一組數(shù)字的和必然是惟一的，因?yàn)椴煌瑪?shù)字的貢獻(xiàn)在不同的十進(jìn)制位上，即使有進(jìn)位，也不會(huì)和其它數(shù)字混淆，因?yàn)槲覀冎豢紤]3個(gè)數(shù)字，很容易就可以窮舉證明這一點(diǎn)。
但這個(gè)變換其實(shí)并不完美，可以再簡(jiǎn)化一下。公式如下：
f(n)=10^n
這樣更簡(jiǎn)單，并且排除了進(jìn)位的可能性，不需窮舉就很容易知道變換的惟一性了。awk程序如下：

1. awk '!a[10^$1+10^$2+10^$3]++'

復(fù)制代碼

b.變換2采用乘法。要保證每個(gè)數(shù)字對(duì)最后結(jié)果的貢獻(xiàn)不相混淆，我們很容易想到采用質(zhì)數(shù)�？梢越ㄒ粋�(gè)表，每一個(gè)數(shù)字從中可以查到惟一的質(zhì)數(shù)，不同的質(zhì)數(shù)相乘結(jié)果自然不會(huì)相同，這很容易理解。公式如下：
f(n)=s[n]
s[n]是一個(gè)包含不同質(zhì)數(shù)的數(shù)組。
awk程序如下：

1. awk '
   
2.   BEGIN {
   
3.     p[0]=2;
   
4.     p[1]=3;
   
5.     p[2]=5;
   
6.     p[3]=7;
   
7.     p[4]=11;
   
8.     p[5]=13;
   
9.     p[6]=17;
   
10.     p[7]=19;
    
11.     p[8]=23;
    
12.     p[9]=29;
    
13.   }
    
14.   !a[p[$1]*p[$2]*p[$3]]++'

復(fù)制代碼

當(dāng)然變換的方式肯定可以有更多，大家可以提出自己的方法。waker兄的
f($1,$2,$3)=$1^9+$2^9+$3^9
f($1,$2,$3)=$1^5+$2^5+$3^5
的思路也不錯(cuò)，只要保證鍵的惟一性就行。

r2007

對(duì)于這種變換f(n)=10^n
只有3個(gè)數(shù)時(shí)，可以這樣變換。f(n)=k^n; k>3
同理當(dāng)有m個(gè)數(shù)據(jù)時(shí)，f(n)=k^n只要k>m
不知對(duì)否？

-_-

原帖由 r2007 于 2006-6-14 19:49 發(fā)表
對(duì)于這種變換f(n)=10^n
只有3個(gè)數(shù)時(shí)，可以這樣變換。f(n)=k^n; k>3
同理當(dāng)有m個(gè)數(shù)據(jù)時(shí)，f(n)=k^n只要k>m
不知對(duì)否？

是否受整型取值范圍影響？

r2007

如果m足夠大，即使求和也會(huì)溢出。在此僅從算法考慮，具體實(shí)現(xiàn)要具體分析。

woodie

原帖由 r2007 于 2006-6-14 19:49 發(fā)表
對(duì)于這種變換f(n)=10^n
只有3個(gè)數(shù)時(shí)，可以這樣變換。f(n)=k^n; k>3
同理當(dāng)有m個(gè)數(shù)據(jù)時(shí)，f(n)=k^n只要k>m
不知對(duì)否？

七兄發(fā)展了我的第一種方法，非常好，這個(gè)很容易證明。謝謝！

woodie

原帖由 -_- 于 2006-6-14 20:04 發(fā)表

是否受整型取值范圍影響？

這個(gè)與數(shù)字的取值范圍關(guān)系不大。^_^

galilette

我來說說加法吧
為了說明方便, 先考慮3個(gè)數(shù)字沒有重復(fù)的情況, 那么最簡(jiǎn)單的就是用`mode bit'方式. 這里假設(shè)<<是類似C中的left shift operator, 那么映射關(guān)系是f(n)=1<<(n-1)=2^(n-1):

1. 
   
2. #digit->bit
   
3. 1  ->  1<<0=1
   
4. 2  ->  1<<1=10
   
5. 3  ->  1<<2=100
   
6. 4  ->  1<<3=1000
   
7. ...
   
8. 9  ->  1<<8
   

復(fù)制代碼

那么每個(gè)沒有重復(fù)數(shù)字的組合, 都可以通過bit or操作實(shí)現(xiàn)疊加, 比如:

1. 
   
2. 235  ->  1<<1|1<<2|1<<4 = 10110
   

復(fù)制代碼

也就是說從右往左, 第2,3,5位是1, 其他是0

如果上面的你看明白了, 那么允許數(shù)字重復(fù)出現(xiàn)的映射也是很簡(jiǎn)單的. 以3個(gè)數(shù)字為例. 如果每個(gè)1都對(duì)應(yīng)二進(jìn)制的1, 那么三個(gè)1就對(duì)應(yīng)1+1+1=3=11(base 2), 顯然每個(gè)數(shù)字最多占用2個(gè)bit, 所以現(xiàn)在2不再對(duì)應(yīng)10, 而是100, 3個(gè)2對(duì)應(yīng)1100, 以此類推. 映射關(guān)系可以表示為 f(n)=1<<(2n-2)=2^(2n-2):

1. 
   
2. 1  ->  1<<0=1
   
3. 2  ->  1<<2=1,00
   
4. 3  ->  1<<4=1,00,00
   
5. 4  ->  1<<6=1,00,00,00
   
6. ...
   
7. 9  ->  1<<16
   

復(fù)制代碼

比如332, 就被轉(zhuǎn)化為1,00,00 + 1,00,00 + 1,00 = 11,01,00. 從右往左2bit一組, 那么第n組就代表了數(shù)字n的狀態(tài), 00, 01, 10, 11分別表示這個(gè)數(shù)字出現(xiàn)了0,1,2,3次

in general, 如果允許n個(gè)重復(fù)數(shù)字, 那么每個(gè)數(shù)字就需要b = 1+int[log_2(n)]個(gè)bit來表示, 比如n=4(100),5(101),6(110),7(111), b=3. f(n)=1<<(b*n-b)=2^(b*n-b), 而且很明顯, 同一b周期內(nèi), 這種編碼的效率在n=2^k-1, k=1,2,...時(shí)最高 (saturation), 在n=2^k時(shí)最低

r2007

精彩
補(bǔ)充一下，樓上似乎忽略了0這種情況
另外：
f(n)=1<<(b*n-b)=2^(b*n-b)等價(jià)于
f(n)=(2^b)^(n-1)
假設(shè)b=3則
f(n)=8^(n-1)

[ 本帖最后由 r2007 于 2006-6-15 13:29 編輯 ]

galilette

嗯, 的確直接8^(n-1)看上去更清楚. 我總是有shift的殘念
關(guān)于0的問題, 我倒是有意`忽略'的, 1-9全extract以后差幾位就表示剩幾個(gè)0了, 所以no information lost, 生成的hash也是唯一的

[ 本帖最后由 galilette 于 2006-6-15 14:04 編輯 ]

r2007

原帖由 galilette 于 2006-6-15 12:27 發(fā)表
n=4(100),5(101),6(110),7(111), b=3. f(n)=1<<(b*n-b)=2^(b*n-b), 而且很明顯, 同一b周期內(nèi), 這種編碼的效率在n=2^k-1, k=1,2,...時(shí)最高 (saturation), 在n=2^k時(shí)最低

剛剛轉(zhuǎn)過來
當(dāng)m=4(100),5(101),6(110),7(111), b=3,則公式為
f(n)=8^(n-1)
其中當(dāng)m=4時(shí)效率最低。
同樣忽略0值，m=4時(shí)：
f(n)=5^(n-1)也可以滿足鍵值唯一的要求。
所以推論最佳公式為：
f(n)=(m+1)^(n-1)