免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 3036 | 回复: 11

一个数字变换的惟一性问题 [复制链接]

论坛徽章:
1
荣誉会员
日期:2011-11-23 16:44:17
发表于 2006-06-14 19:31 |显示全部楼层
问题的缘起是技安网友提的一个问题,大意是一个文件中的每行有3个十进数字,相同的组合但顺序不同视为重复,只保留其中一种组合,其余不同排列方式的行删除。这个帖子有许多网友参加讨论并且当时已经认为被解决了,实际上其中一种用awk的解法是有些遗漏的。最近技安网友发现了这个问题并再次发贴求助,很遗憾由于相互产生了一些误解,搞得有些不愉快。其实大可不必,上论坛是来交流的,又不是斗气的,大家最好就事论事。就算错了也没什么大不了,小弟我就经常犯错——不好意思,有些还是低级错误,所以脸皮也混得越来越厚了。窃以为能承认错误是有肚量、有风度的体现。怎么样我脸皮够厚吧,这不是绕着弯表扬自己嘛?嘿嘿^_^。其实人非圣贤,孰能无过?大家哈哈一笑揭过算了,千万别伤了和气。

参考帖:
1.技安兄首次提问
2.技安兄二次提问

玩笑开过了,咱们言归正传。

用awk解决类似问题的思路一般是使用所谓的“关联数组”,实际上就是hash表,键是数组下标,值就是数组的值。程序大致上是这样:
  1. awk '!array[key]++'
复制代码

这等价于
  1. awk '!array[key]++{print $0}'
复制代码

当key对应的值不存在时设置这个键值(++操作使该数组元素由0变为1),并打印当前行;当对应的键值存在时表示已经有相应的记录存在,则不打印当前行。这就保证了键值惟一时对应输出行的惟一。

于是用awk解决这个问题的关键就是如何构造hash键的问题了。即是将文件中所有行变换到一个键的集合,对于这个问题,不同数字的组合得到的键应当不同;反之就可能遗漏掉一些有效的组合。那么如何构造呢?不同的人可能有不同的方法,但只要能证明变换的惟一性就行了,穷举法证明也行。

我的思路是:首先将变换分为两部分,单个数字的变换(简记为变换1)和3个数字综合的变换(简记为变换2)。
1.由于几个数字的顺序是不重要的,类比数学中的运算加法和乘法都满足交换率,所以各个加数和因子的顺序也是不重要的。所以变换2可以采用加法或乘法运算,将每一个数字的变换结果连结起来,如此就可以满足顺序无关的条件。
2.那如何选择变换1的形式,并且保证最终变换的惟一性呢?我想到两个方法:
a.一个是变换2使用加法运算的,我在参考贴2的8楼已经给出了一种形式:
就是将每个数字后面加上若干个0,即0变成0,1变成10,2变成200,3变成3000,...依此类推,9变成9x10^9。
f(n)=n*10^n
这样可以保证同一组数字的和必然是惟一的,因为不同数字的贡献在不同的十进制位上,即使有进位,也不会和其它数字混淆,因为我们只考虑3个数字,很容易就可以穷举证明这一点。
但这个变换其实并不完美,可以再简化一下。公式如下:
f(n)=10^n
这样更简单,并且排除了进位的可能性,不需穷举就很容易知道变换的惟一性了。awk程序如下:
  1. awk '!a[10^$1+10^$2+10^$3]++'
复制代码

b.变换2采用乘法。要保证每个数字对最后结果的贡献不相混淆,我们很容易想到采用质数。可以建一个表,每一个数字从中可以查到惟一的质数,不同的质数相乘结果自然不会相同,这很容易理解。公式如下:
f(n)=s[n]
s[n]是一个包含不同质数的数组。
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]]++'
复制代码


当然变换的方式肯定可以有更多,大家可以提出自己的方法。waker兄的
f($1,$2,$3)=$1^9+$2^9+$3^9
f($1,$2,$3)=$1^5+$2^5+$3^5
的思路也不错,只要保证键的惟一性就行。

评分

参与人数 1可用积分 +5 收起 理由
r2007 + 5

查看全部评分

论坛徽章:
7
荣誉版主
日期:2011-11-23 16:44:17子鼠
日期:2014-07-24 15:38:07狮子座
日期:2014-07-24 11:00:54巨蟹座
日期:2014-07-21 19:03:10双子座
日期:2014-05-22 12:00:09卯兔
日期:2014-05-08 19:43:17卯兔
日期:2014-08-22 13:39:09
发表于 2006-06-14 19:49 |显示全部楼层
对于这种变换f(n)=10^n
只有3个数时,可以这样变换。f(n)=k^n; k>3
同理当有m个数据时,f(n)=k^n只要k>m
不知对否?

论坛徽章:
0
发表于 2006-06-14 20:04 |显示全部楼层
原帖由 r2007 于 2006-6-14 19:49 发表
对于这种变换f(n)=10^n
只有3个数时,可以这样变换。f(n)=k^n; k>3
同理当有m个数据时,f(n)=k^n只要k>m
不知对否?

是否受整型取值范围影响?

论坛徽章:
7
荣誉版主
日期:2011-11-23 16:44:17子鼠
日期:2014-07-24 15:38:07狮子座
日期:2014-07-24 11:00:54巨蟹座
日期:2014-07-21 19:03:10双子座
日期:2014-05-22 12:00:09卯兔
日期:2014-05-08 19:43:17卯兔
日期:2014-08-22 13:39:09
发表于 2006-06-15 11:33 |显示全部楼层
如果m足够大,即使求和也会溢出。在此仅从算法考虑,具体实现要具体分析。

论坛徽章:
1
荣誉会员
日期:2011-11-23 16:44:17
发表于 2006-06-15 12:19 |显示全部楼层
原帖由 r2007 于 2006-6-14 19:49 发表
对于这种变换f(n)=10^n
只有3个数时,可以这样变换。f(n)=k^n; k>3
同理当有m个数据时,f(n)=k^n只要k>m
不知对否?

七兄发展了我的第一种方法,非常好,这个很容易证明。谢谢!

论坛徽章:
1
荣誉会员
日期:2011-11-23 16:44:17
发表于 2006-06-15 12:21 |显示全部楼层
原帖由 -_- 于 2006-6-14 20:04 发表

是否受整型取值范围影响?

这个与数字的取值范围关系不大。^_^

论坛徽章:
0
发表于 2006-06-15 12:27 |显示全部楼层
我来说说加法吧
为了说明方便, 先考虑3个数字没有重复的情况, 那么最简单的就是用`mode bit'方式. 这里假设<<是类似C中的left shift operator, 那么映射关系是f(n)=1<<(n-1)=2^(n-1):

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

那么每个没有重复数字的组合, 都可以通过bit or操作实现叠加, 比如:

  1. 235  ->  1<<1|1<<2|1<<4 = 10110
复制代码

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

如果上面的你看明白了, 那么允许数字重复出现的映射也是很简单的. 以3个数字为例. 如果每个1都对应二进制的1, 那么三个1就对应1+1+1=3=11(base 2), 显然每个数字最多占用2个bit, 所以现在2不再对应10, 而是100, 3个2对应1100, 以此类推. 映射关系可以表示为 f(n)=1<<(2n-2)=2^(2n-2):

  1. 1  ->  1<<0=1
  2. 2  ->  1<<2=1,00
  3. 3  ->  1<<4=1,00,00
  4. 4  ->  1<<6=1,00,00,00
  5. ...
  6. 9  ->  1<<16
复制代码

比如332, 就被转化为1,00,00 + 1,00,00 + 1,00 = 11,01,00. 从右往左2bit一组, 那么第n组就代表了数字n的状态, 00, 01, 10, 11分别表示这个数字出现了0,1,2,3次

in general, 如果允许n个重复数字, 那么每个数字就需要b = 1+int[log_2(n)]个bit来表示, 比如n=4(100),5(101),6(110),7(111), b=3. f(n)=1<<(b*n-b)=2^(b*n-b), 而且很明显, 同一b周期内, 这种编码的效率在n=2^k-1, k=1,2,...时最高 (saturation), 在n=2^k时最低

论坛徽章:
7
荣誉版主
日期:2011-11-23 16:44:17子鼠
日期:2014-07-24 15:38:07狮子座
日期:2014-07-24 11:00:54巨蟹座
日期:2014-07-21 19:03:10双子座
日期:2014-05-22 12:00:09卯兔
日期:2014-05-08 19:43:17卯兔
日期:2014-08-22 13:39:09
发表于 2006-06-15 13:20 |显示全部楼层

回复 7楼 galilette 的帖子

精彩
补充一下,楼上似乎忽略了0这种情况
另外:
f(n)=1<<(b*n-b)=2^(b*n-b)等价于
f(n)=(2^b)^(n-1)
假设b=3则
f(n)=8^(n-1)

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

论坛徽章:
0
发表于 2006-06-15 14:02 |显示全部楼层
嗯, 的确直接8^(n-1)看上去更清楚. 我总是有shift的残念
关于0的问题, 我倒是有意`忽略'的, 1-9全extract以后差几位就表示剩几个0了, 所以no information lost, 生成的hash也是唯一的

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

论坛徽章:
7
荣誉版主
日期:2011-11-23 16:44:17子鼠
日期:2014-07-24 15:38:07狮子座
日期:2014-07-24 11:00:54巨蟹座
日期:2014-07-21 19:03:10双子座
日期:2014-05-22 12:00:09卯兔
日期:2014-05-08 19:43:17卯兔
日期:2014-08-22 13:39:09
发表于 2006-06-15 14:19 |显示全部楼层
原帖由 galilette 于 2006-6-15 12:27 发表
n=4(100),5(101),6(110),7(111), b=3. f(n)=1<<(b*n-b)=2^(b*n-b), 而且很明显, 同一b周期内, 这种编码的效率在n=2^k-1, k=1,2,...时最高 (saturation), 在n=2^k时最低

刚刚转过来
当m=4(100),5(101),6(110),7(111), b=3,则公式为
f(n)=8^(n-1)
其中当m=4时效率最低。
同样忽略0值,m=4时:
f(n)=5^(n-1)也可以满足键值唯一的要求。
所以推论最佳公式为:
f(n)=(m+1)^(n-1)
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP