Verhoeff算法的正确排列循环

5

我正在实现Verhoeff算法作为一种校验位方案,但是网络来源之间似乎存在一些争议,关于哪个置换循环应该成为置换表的基础。

维基百科使用:(36)(01589427)

显然, Numerical Recipies 使用了不同的循环,这本书使用的是:(0)(14)(23)(56789),引用自Winters在1990年发表的一篇文章。它还指出,Verhoeff使用了维基百科引用的那个循环。

现在,我的数论有点生疏,但是维基百科的循环明显会在第8次幂后重复,而书中的循环则需要10次幂,尽管它说s^8=s。表2.14(b)在2-循环方面还存在其他错误,所以这是可疑的。

很遗憾,我没有原始文章的副本(并且太紧了,不想支付/对40年前的知识仍被出版商绑架感到恶心),也没有 Numerical Recipes 的副本来检查(而且我不愿安装他们的偏执引起的拷贝保护插件来在线查看)。

那么有人知道哪个是正确的吗?它们都正确吗?

2个回答

3

这里有一份旧版的Numerical Recipes的PDF版本链接。第20.3节介绍了Verhoeff算法,其使用的排列方式与维基百科文章相同。


谢谢你的回复,但据我所知,那里使用的排列表是完全错误的。恒等排列不在其中,其他条目甚至不是排列(元素出现多次)。 - James
@James:这个排列和维基百科的完全相同,只是按列排列而不是按行排列。如果您查看维基百科排列表的列,您将得到与NR使用的完全相同的值。NR混乱地格式化了表格,因为他们将数字分成了10组,而应该将其分成8组。 - interjay
啊,我现在明白了。他们还把不同矩阵之间的方向也换了,这也没有帮助…… - James

2

排列(0)(14)(23)(56789)比排列(36)(01589427)更好。这是因为(36)(01589427)只能检测到88.89%的单个置换错误,而(0)(14)(23)(56789)可以检测到所有的错误。考虑当数字代码716被给定0作为校验位时,如果使用(36)(01589427),即使1和6被置换,该校验位方案也不会出现错误,因为校验和为0。但是,(0)(14)(23)(56789)则不然。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接