ciclo di permutazione corretto per l'algoritmo Verhoeff

Question

sto implementando l'algoritmo Verhoeff per uno schema cifra di controllo, ma sembra che ci sia qualche disaccordo in fonti web su quale ciclo di permutazione dovrebbe costituire la base della tabella di permutazione.

usi Wikipedia : (36) (01.589.427)

apparentemente , numerica Ricette utilizza un ciclo diverso e noreferrer questo libro usi: (0) (14) ( 23) (56789), citato da un articolo di 1990 Winters. Ha anche note che Verhoeff usato le citazioni uno Wikipedia.

Ora, la mia teoria dei numeri è un po 'arrugginito, ma il ciclo Wikipedia chiaramente si ripete dopo l'8 di potenza, mentre il libro vi potrà togliere 10, nonostante dicendo che s ^ 8 = s. Tabella 2.14 (b) ha altri errori nei 2-cicli, quindi questo è dubbia comunque.

Purtroppo, non ho copie degli articoli originali (e sono troppo stretto per pagare / disgustato che il 40-year old conoscenza è ancora detenuto in ostaggio dagli editori), né una copia di Numerical Recipes per controllare (e sono restio a installare la loro paranoia indotta protezione da copia del plug-in di visualizzazione on-line).

Così fa Uno sa che è corretto? Sono entrambi corretti?

Answer 1

C'è una vecchia edizione di Numerical Recipes disponibili qui in formato PDF. Verhoeff algoritmo è descritto nel paragrafo 20.3. Esso utilizza la stessa permutazione come l'articolo di Wikipedia.

Answer 2

La permutazione (0) (14) (23) (56789) è migliore di permutazione (36) (01.589.427). Questo perché, (36) (01.589.427) può rilevare solo 88.89% degli errori singola trasposizione mentre (0) (14) (23) (56789) in grado di rilevare tutti loro. Si consideri il codice numerico 716 essere dato 0 come cifra di controllo se viene usato (36) (01.589.427). cioè, il codice sarà 7160. Ma, se le cifre 1 e 6 sono trasposti, questo schema cifra di controllo non dà un errore come la somma di controllo è zero. Questo non è il caso con (0) (14) (23) (56789).