Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Correct permutation cycle for Verhoeff algorithm

I'm implementing the Verhoeff algorithm for a check digit scheme, but there seems to be some disagreement in web sources as to which permutation cycle should form the basis of the permutation table.

Wikipedia uses: (36)(01589427)

while apparently, Numerical Recipies uses a different cycle and this book uses: (0)(14)(23)(56789), quoted from a 1990 article by Winters. It also notes that Verhoeff used the one Wikipedia quotes.

Now, my number theory is a little rusty, but the Wikipedia cycle clearly will repeat after the 8th power, while the book one will take 10, despite it saying that s^8=s. Table 2.14(b) has other errors in the 2-cycles, so this is dubious anyway.

Unfortunately, I don't have copies of the original articles (and am too tight to pay/disgusted that 40-year old knowledge is still being held to ransom by publishers), nor a copy of Numerical Recipes to check (and am loath to install their paranoia-induced copy protection plug-in to view online).

So does any one know which is correct? Are they both correct?

like image 738
James Avatar asked May 20 '10 10:05

James


2 Answers

There's an old edition of Numerical Recipes available here as PDFs. Verhoeff algorithm is described in section 20.3. It uses the same permutation as the Wikipedia article.

like image 161
interjay Avatar answered Nov 15 '22 22:11

interjay


The permutation (0)(14)(23)(56789) is better than the permutation (36)(01589427). This is because, (36)(01589427) can only detect 88.89% of the single transposition errors while (0)(14)(23)(56789) can detect all of them. Consider the numeric code 716 be given 0 as the check digit if (36)(01589427) is used. i.e., the code will be 7160. But, if the digits 1 and 6 are transposed, this check digit scheme does not give an error as the check sum is zero. This is not the case with (0)(14)(23)(56789).

like image 2
A Siddharth Avatar answered Nov 15 '22 21:11

A Siddharth