Talk:Verhoeff algorithm
Is this algorithm correct?
According to [1], 3170092 is also a valid number.
Using the algorithm here, that becomes:
| i | ni | p(i,ni) | previous c | new c = d(c,p(i,ni)) |
|---|---|---|---|---|
| 0 | 2 | 2 | 0 | 2 |
| 1 | 9 | 4 | 2 | 1 |
| 2 | 0 | 5 | 1 | 6 |
| 3 | 0 | 8 | 6 | 3 |
| 4 | 7 | 8 | 3 | 6 |
| 5 | 1 | 2 | 6 | 9 |
| 6 | 3 | 3 | 9 | 6 |
Which one is incorrect? The wikiarticle? The other article? The fact that 3170092 is a valid number? Or have I made a mistake?
- As best I can tell, the Marist College article you cited is wrong. The position-based permutation which Verhoeff settled on (the p table) is not a simple exponential of the group multiplication (the d table), as the article you found claims.
- My understanding (from the first reference in the Wikipedia article) is that Verhoeff experimented with many different permutations before coming up with one that worked particularly well. A simple exponential permutation would actually be atrociously bad, since multiplication in the dihedral group contains two cycles of period 2 — namely, (14) and (23) — and one cycle of period 1 — namely, (0).