Перейти к содержанию

Реализации алгоритмов/Алгоритм Верхуффа

Добавить ссылки
Материал из Викиучебника — открытых книг для открытого мира
Логотип Википедии
Логотип Википедии

В Википедии имеется статья по теме «Алгоритм Верхуффа»

Алгоритм Верхуффа (англ. Verhoeff algorithm) — алгоритм расчёта контрольной цифры для обнаружения ошибок при ручном вводе длинных цифровых последовательностей. Алгоритм позволяет выявить большее число ошибок, нежели аналогичный алгоритм Луна.


C

[править]
// Таблица умножения
static int verhoeff_d[][]  = {
  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
  {1, 2, 3, 4, 0, 6, 7, 8, 9, 5},
  {2, 3, 4, 0, 1, 7, 8, 9, 5, 6},
  {3, 4, 0, 1, 2, 8, 9, 5, 6, 7},
  {4, 0, 1, 2, 3, 9, 5, 6, 7, 8},
  {5, 9, 8, 7, 6, 0, 4, 3, 2, 1},
  {6, 5, 9, 8, 7, 1, 0, 4, 3, 2},
  {7, 6, 5, 9, 8, 2, 1, 0, 4, 3},
  {8, 7, 6, 5, 9, 3, 2, 1, 0, 4},
  {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
};

// Таблица перестановок
static int verhoeff_p[][]= {
  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
  {1, 5, 7, 6, 2, 8, 3, 0, 9, 4},
  {5, 8, 0, 3, 7, 9, 6, 1, 4, 2},
  {8, 9, 1, 6, 0, 4, 3, 5, 2, 7},
  {9, 4, 5, 3, 1, 2, 6, 8, 7, 0},
  {4, 2, 8, 6, 5, 7, 3, 9, 0, 1},
  {2, 7, 9, 3, 8, 0, 6, 4, 1, 5},
  {7, 0, 4, 6, 9, 1, 3, 2, 5, 8}
};

// Обратная таблица
static int verhoeff_inv[] = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9};

// For a given number generates a Verhoeff digit
static int generate_verhoeff(const char* num)
{
  int c;
  int len;
  c = 0;
  len = strlen(num);

  for(int i = 0; i < len; i++)
    c = verhoeff_d[c][verhoeff_p[((i + 1) % 8)][num[len - i - 1] - '0']];

  return verhoeff_inv[c];
}

//Validates that an entered number is Verhoeff compliant.
//The check digit must be the last one.
static int validate_verhoeff(const char*  num)
{
  int c;
  int len;
  c = 0;
  len = strlen(num);

  for (int i = 0; i < len; i++)
    c = verhoeff_d[c][verhoeff_p[(i % 8)][num[len - i - 1] - '0']];

  return (c == 0);
}

C#

[править]
    /// <summary>
    /// For more information cf. http://en.wikipedia.org/wiki/Verhoeff_algorithm
    /// Dihedral Group stuff: http://en.wikipedia.org/wiki/Dihedral_group
    /// Dihedral Group order 10: http://mathworld.wolfram.com/DihedralGroupD5.html
    /// </summary>
    public static class Verhoeff
    {        

        // The multiplication table
        static int[,] d  = new int[,]
        {
            {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 
            {1, 2, 3, 4, 0, 6, 7, 8, 9, 5}, 
            {2, 3, 4, 0, 1, 7, 8, 9, 5, 6}, 
            {3, 4, 0, 1, 2, 8, 9, 5, 6, 7}, 
            {4, 0, 1, 2, 3, 9, 5, 6, 7, 8}, 
            {5, 9, 8, 7, 6, 0, 4, 3, 2, 1}, 
            {6, 5, 9, 8, 7, 1, 0, 4, 3, 2}, 
            {7, 6, 5, 9, 8, 2, 1, 0, 4, 3}, 
            {8, 7, 6, 5, 9, 3, 2, 1, 0, 4}, 
            {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
        };

        // The permutation table
        static int[,] p = new int[,]
        {
            {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 
            {1, 5, 7, 6, 2, 8, 3, 0, 9, 4}, 
            {5, 8, 0, 3, 7, 9, 6, 1, 4, 2}, 
            {8, 9, 1, 6, 0, 4, 3, 5, 2, 7}, 
            {9, 4, 5, 3, 1, 2, 6, 8, 7, 0}, 
            {4, 2, 8, 6, 5, 7, 3, 9, 0, 1}, 
            {2, 7, 9, 3, 8, 0, 6, 4, 1, 5}, 
            {7, 0, 4, 6, 9, 1, 3, 2, 5, 8}
        };

        // The inverse table
        static int[] inv = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9};


        /// <summary>
        /// Validates that an entered number is Verhoeff compliant.
        /// NB: Make sure the check digit is the last one!
        /// </summary>
        /// <param name="num"></param>
        /// <returns>True if Verhoeff compliant, otherwise false</returns>
        public static bool validateVerhoeff(string num)
        {
            int c = 0;
            int[] myArray = StringToReversedIntArray(num);

            for (int i = 0; i < myArray.Length; i++)
            {
                c = d[c, p[(i % 8), myArray[i]]];
            }

            return c == 0;

        }

        /// <summary>
        /// For a given number generates a Verhoeff digit
        /// Append this check digit to num
        /// </summary>
        /// <param name="num"></param>
        /// <returns>Verhoeff check digit as string</returns>
        public static string generateVerhoeff(string num)
        {
            int c = 0;
            int[] myArray = StringToReversedIntArray(num);

            for (int i = 0; i < myArray.Length; i++)
            {
                c = d[c, p[((i + 1) % 8), myArray[i]]];
            }

            return inv[c].ToString();
        }


        /// <summary>
        /// Converts a string to a reversed integer array.
        /// </summary>
        /// <param name="num"></param>
        /// <returns>Reversed integer array</returns>
        private static int[] StringToReversedIntArray(string num)
        {
            int[] myArray = new int[num.Length];    

            for(int i = 0; i < num.Length; i++)
            {
                myArray[i] = int.Parse(num.Substring(i, 1));
            }

            Array.Reverse(myArray);

            return myArray;

        }
    }

VB.NET

[править]
''' <summary>
''' For more information cf. http://en.wikipedia.org/wiki/Verhoeff_algorithm
''' Dihedral Group: http://mathworld.wolfram.com/DihedralGroup.html
''' </summary>
''' <remarks></remarks>
Public Class Verhoeff


    'The multiplication table
    Shared ReadOnly d(,) As Integer = _
    {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, _
    {1, 2, 3, 4, 0, 6, 7, 8, 9, 5}, _
    {2, 3, 4, 0, 1, 7, 8, 9, 5, 6}, _
    {3, 4, 0, 1, 2, 8, 9, 5, 6, 7}, _
    {4, 0, 1, 2, 3, 9, 5, 6, 7, 8}, _
    {5, 9, 8, 7, 6, 0, 4, 3, 2, 1}, _
    {6, 5, 9, 8, 7, 1, 0, 4, 3, 2}, _
    {7, 6, 5, 9, 8, 2, 1, 0, 4, 3}, _
    {8, 7, 6, 5, 9, 3, 2, 1, 0, 4}, _
    {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}}

    'The permutation table
    Shared ReadOnly p(,) As Integer = _
    {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, _
    {1, 5, 7, 6, 2, 8, 3, 0, 9, 4}, _
    {5, 8, 0, 3, 7, 9, 6, 1, 4, 2}, _
    {8, 9, 1, 6, 0, 4, 3, 5, 2, 7}, _
    {9, 4, 5, 3, 1, 2, 6, 8, 7, 0}, _
    {4, 2, 8, 6, 5, 7, 3, 9, 0, 1}, _
    {2, 7, 9, 3, 8, 0, 6, 4, 1, 5}, _
    {7, 0, 4, 6, 9, 1, 3, 2, 5, 8}}

    'The inverse table
    Shared ReadOnly inv() As Integer = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9}



    ''' <summary>
    ''' Validates that an entered number is Verhoeff compliant.
    ''' </summary>
    ''' <param name="num"></param>
    ''' <returns>True if Verhoeff compliant, otherwise false</returns>
    ''' <remarks>Make sure the check digit is the last one!</remarks>
    Public Shared Function validateVerhoeff(ByVal num As String) As Boolean

        Dim c As Integer = 0
        Dim myArray() As Integer = StringToReversedIntArray(num)

        For i As Integer = 0 To myArray.Length - 1
            c = d(c, p((i Mod 8), myArray(i)))
        Next i

        Return c.Equals(0)

    End Function


    ''' <summary>
    ''' For a given number generates a Verhoeff digit
    ''' </summary>
    ''' <param name="num"></param>
    ''' <returns>Verhoeff check digit as string</returns>
    ''' <remarks>Append this check digit to num</remarks>
    Public Shared Function generateVerhoeff(ByVal num As String) As String

        Dim c As Integer = 0
        Dim myArray() As Integer = StringToReversedIntArray(num)

        For i As Integer = 0 To myArray.Length - 1
            c = d(c, p(((i + 1) Mod 8), myArray(i)))
        Next i

        Return inv(c).ToString

    End Function


    ''' <summary>
    ''' Converts a string to a reversed integer array.
    ''' </summary>
    ''' <param name="str"></param>
    ''' <returns>Reversed integer array</returns>
    ''' <remarks></remarks>
    Private Shared Function StringToReversedIntArray(ByVal str As String) As Integer()

        Dim myArray(str.Length - 1) As Integer

        For i As Integer = 0 To str.Length - 1
            myArray(i) = Convert.ToInt16(str.Substring(i, 1))
            'we could use myArray(i) = Convert.ToInt16(str(i)) - 48 '48 is from Convert.ToInt16("0"c)
        Next

        Array.Reverse(myArray)

        Return myArray

        'A more modern version of this may look something like this
        'Return (From I In str.ToArray
        '        Select CInt(I.ToString)).Reverse.ToArray

    End Function

End Class

VB for Applications

[править]
''' <summary>
''' For more information cf. http://en.wikipedia.org/wiki/Verhoeff_algorithm
''' Dihedral Group: http://mathworld.wolfram.com/DihedralGroup.html
''' You can use this code in Excel, Access, etc...
''' </summary>
''' <remarks></remarks>
 
'The multiplication table
Dim d(0 To 9) As Variant
'The permutation table
Dim p(0 To 8) As Variant
'The inverse table
Dim inv(0 To 9) As Integer

Private Sub initVerhoeffConsts()
    If IsArray(d(0)) Then Exit Sub 'Shortcut if already initiated
    d(0) = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
    d(1) = Array(1, 2, 3, 4, 0, 6, 7, 8, 9, 5)
    d(2) = Array(2, 3, 4, 0, 1, 7, 8, 9, 5, 6)
    d(3) = Array(3, 4, 0, 1, 2, 8, 9, 5, 6, 7)
    d(4) = Array(4, 0, 1, 2, 3, 9, 5, 6, 7, 8)
    d(5) = Array(5, 9, 8, 7, 6, 0, 4, 3, 2, 1)
    d(6) = Array(6, 5, 9, 8, 7, 1, 0, 4, 3, 2)
    d(7) = Array(7, 6, 5, 9, 8, 2, 1, 0, 4, 3)
    d(8) = Array(8, 7, 6, 5, 9, 3, 2, 1, 0, 4)
    d(9) = Array(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
   
    p(0) = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
    p(1) = Array(1, 5, 7, 6, 2, 8, 3, 0, 9, 4)
    p(2) = Array(5, 8, 0, 3, 7, 9, 6, 1, 4, 2)
    p(3) = Array(8, 9, 1, 6, 0, 4, 3, 5, 2, 7)
    p(4) = Array(9, 4, 5, 3, 1, 2, 6, 8, 7, 0)
    p(5) = Array(4, 2, 8, 6, 5, 7, 3, 9, 0, 1)
    p(6) = Array(2, 7, 9, 3, 8, 0, 6, 4, 1, 5)
    p(7) = Array(7, 0, 4, 6, 9, 1, 3, 2, 5, 8)

    inv(0) = 0: inv(1) = 4: inv(2) = 3: inv(3) = 2: inv(4) = 1
    inv(5) = 5: inv(6) = 6: inv(7) = 7: inv(8) = 8: inv(9) = 9
End Sub
 
 
''' <summary>
''' Validates that an entered number is Verhoeff compliant.
''' </summary>
''' <param name="num"></param>
''' <returns>True if Verhoeff compliant, otherwise false</returns>
''' <remarks>Make sure the check digit is the last one!</remarks>
Public Function validateVerhoeff(ByVal num As String) As Boolean
        initVerhoeffConsts
        Dim c As Integer
        Dim i As Integer
        c = 0
        Dim myArray() As Integer
        myArray = StringToReversedIntArray(num)
 
        For i = 0 To UBound(myArray)
            c = d(c)(p((i Mod 8))(myArray(i)))  'Version corrected by WHG gives error
        Next i
 
        validateVerhoeff = (c = 0)
End Function
 
 
''' <summary>
''' For a given number generates a Verhoeff digit
''' </summary>
''' <param name="num"></param>
''' <returns>Verhoeff check digit as Integer</returns>
''' <remarks>Append this check digit to num</remarks>
Public Function generateVerhoeff(ByVal num As String) As Integer
    initVerhoeffConsts
    Dim c As Integer
    Dim i As Integer    
    c = 0
    Dim myArray() As Integer
    myArray = StringToReversedIntArray(num)

    For i = 0 To UBound(myArray)
        c = d(c)(p((i + 1) Mod 8)(myArray(i)))   'Version corrected by WHG gives error in compilation
    Next i

    generateVerhoeff = inv(c) 'str(inv(c))
End Function
 
 
''' <summary>
''' Converts a string to a reversed integer array.
''' </summary>
''' <param name="str"></param>
''' <returns>Reversed integer array</returns>
''' <remarks></remarks>
Private Function StringToReversedIntArray(ByVal str As String) As Integer()
    Dim lg As Integer
    lg = Len(str)
    Dim myArray() As Integer
    ReDim myArray(0 To lg - 1)
    Dim i As Integer
    
    For i = 0 To lg - 1
        myArray(i) = AscW(Mid$(str, lg - i, 1)) - AscW("0")
    Next
    StringToReversedIntArray = myArray
End Function

''' In Excel don't copy this sub _AssertsVerhoeff()as get a compilation error. 4/21/2013
Public Sub _AssertsVerhoeff()
    Debug.Print "Start Verhoeff's Asserts"
    Debug.Assert generateVerhoeff("75872") = 2
    Debug.Assert validateVerhoeff("758722") = True
    Debug.Assert generateVerhoeff("12345") = 1
    Debug.Assert validateVerhoeff("123451") = True
    Debug.Assert generateVerhoeff("142857") = 0
    Debug.Assert validateVerhoeff("1428570") = True
    Debug.Assert generateVerhoeff("123456789012") = 0
    Debug.Assert validateVerhoeff("1234567890120") = True
    Debug.Assert generateVerhoeff("8473643095483728456789") = 2
    Debug.Assert validateVerhoeff("84736430954837284567892") = True
    Debug.Assert generateVerhoeff("12345") = 1
    Debug.Assert validateVerhoeff("123451") = True
    Debug.Assert validateVerhoeff("124351") = False
    Debug.Assert validateVerhoeff("122451") = False
    Debug.Assert validateVerhoeff("128451") = False
    Debug.Assert validateVerhoeff("214315") = False
    Debug.Print "End Verhoeff's Asserts"
End Sub

Java

[править]
/**
 * @see <a href="http://en.wikipedia.org/wiki/Verhoeff_algorithm">More Info</a>
 * @see <a href="http://en.wikipedia.org/wiki/Dihedral_group">Dihedral Group</a>
 * @see <a href="http://mathworld.wolfram.com/DihedralGroupD5.html">Dihedral Group Order 10</a>
 * @author Colm Rice
 */
public class Verhoeff {

		
    // The multiplication table
    static int[][] d  = new int[][]
    {
        {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 
        {1, 2, 3, 4, 0, 6, 7, 8, 9, 5}, 
        {2, 3, 4, 0, 1, 7, 8, 9, 5, 6}, 
        {3, 4, 0, 1, 2, 8, 9, 5, 6, 7}, 
        {4, 0, 1, 2, 3, 9, 5, 6, 7, 8}, 
        {5, 9, 8, 7, 6, 0, 4, 3, 2, 1}, 
        {6, 5, 9, 8, 7, 1, 0, 4, 3, 2}, 
        {7, 6, 5, 9, 8, 2, 1, 0, 4, 3}, 
        {8, 7, 6, 5, 9, 3, 2, 1, 0, 4}, 
        {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
    };
	
    // The permutation table
    static int[][] p = new int[][]
    {
        {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 
        {1, 5, 7, 6, 2, 8, 3, 0, 9, 4}, 
        {5, 8, 0, 3, 7, 9, 6, 1, 4, 2}, 
        {8, 9, 1, 6, 0, 4, 3, 5, 2, 7}, 
        {9, 4, 5, 3, 1, 2, 6, 8, 7, 0}, 
        {4, 2, 8, 6, 5, 7, 3, 9, 0, 1}, 
        {2, 7, 9, 3, 8, 0, 6, 4, 1, 5}, 
        {7, 0, 4, 6, 9, 1, 3, 2, 5, 8}
    };
	
    // The inverse table
    static int[] inv = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9};
	
    
    /* 
     * For a given number generates a Verhoeff digit
     * 
     */
	public static String generateVerhoeff(String num){
			
		int c = 0;
		int[] myArray = StringToReversedIntArray(num);
		
		for(int i = 0; i < myArray.length; i++)
		{
			c = d[c][p[((i + 1) % 8)] [myArray[i]]];
		}
		
		return Integer.toString(inv[c]);
	}
	
	
	/*
	 * Validates that an entered number is Verhoeff compliant.
	 * NB: Make sure the check digit is the last one.
	 */
	public static boolean validateVerhoeff(String num){
		
        	int c = 0;
        	int[] myArray = StringToReversedIntArray(num);
        
        	for (int i = 0; i < myArray.length; i++)
        	{
        		c = d[c][p[(i % 8)][myArray[i]]];
        	}
		
		return (c == 0);
	}
	
	

	/*
	 * Converts a string to a reversed integer array.
	 */
	private static int[] StringToReversedIntArray(String num){
		
		int[] myArray = new int[num.length()];
		
		for(int i = 0; i < num.length(); i++)
		{
			myArray[i] = Integer.parseInt(num.substring(i, i + 1));					
		}
		
		myArray = Reverse(myArray);
		
		return myArray;
	
	}
	
	/*
	 * Reverses an int array
	 */
	private static int[] Reverse(int[] myArray)
	{
		int[] reversed = new int[myArray.length];
		
		for(int i = 0; i < myArray.length ; i++)
		{
			reversed[i] = myArray[myArray.length - (i + 1)];			
		}
				
		return reversed;
	}
	
	
}

Python

[править]
# @see <a href="http://en.wikipedia.org/wiki/Verhoeff_algorithm">More Info</a>
# @see <a href="http://en.wikipedia.org/wiki/Dihedral_group">Dihedral Group</a>
# @see <a href="http://mathworld.wolfram.com/DihedralGroupD5.html">Dihedral Group Order 10</a>
# @author Hermann Himmelbauer

verhoeff_table_d = (
    (0,1,2,3,4,5,6,7,8,9),
    (1,2,3,4,0,6,7,8,9,5),
    (2,3,4,0,1,7,8,9,5,6),
    (3,4,0,1,2,8,9,5,6,7),
    (4,0,1,2,3,9,5,6,7,8),
    (5,9,8,7,6,0,4,3,2,1),
    (6,5,9,8,7,1,0,4,3,2),
    (7,6,5,9,8,2,1,0,4,3),
    (8,7,6,5,9,3,2,1,0,4),
    (9,8,7,6,5,4,3,2,1,0))
verhoeff_table_p = (
    (0,1,2,3,4,5,6,7,8,9),
    (1,5,7,6,2,8,3,0,9,4),
    (5,8,0,3,7,9,6,1,4,2),
    (8,9,1,6,0,4,3,5,2,7),
    (9,4,5,3,1,2,6,8,7,0),
    (4,2,8,6,5,7,3,9,0,1),
    (2,7,9,3,8,0,6,4,1,5),
    (7,0,4,6,9,1,3,2,5,8))
verhoeff_table_inv = (0,4,3,2,1,5,6,7,8,9)

def calcsum(number):
    """For a given number returns a Verhoeff checksum digit"""
    c = 0
    for i, item in enumerate(reversed(str(number))):
        c = verhoeff_table_d[c][verhoeff_table_p[(i+1)%8][int(item)]]
    return verhoeff_table_inv[c]

def checksum(number):
    """For a given number generates a Verhoeff digit and
    returns number + digit"""
    c = 0
    for i, item in enumerate(reversed(str(number))):
        c = verhoeff_table_d[c][verhoeff_table_p[i % 8][int(item)]]
    return c

def generateVerhoeff(number):
    """For a given number returns number + Verhoeff checksum digit"""
    return "%s%s" % (number, calcsum(number))

def validateVerhoeff(number):
    """Validate Verhoeff checksummed number (checksum is last digit)"""
    return checksum(number) == 0

# Some tests and also usage examples
assert calcsum('75872') == 2
assert checksum('758722') == 0
assert calcsum('12345') == 1
assert checksum('123451') == 0
assert calcsum('142857') == 0
assert checksum('1428570') == 0
assert calcsum('123456789012') == 0
assert checksum('1234567890120') == 0
assert calcsum('8473643095483728456789') == 2
assert checksum('84736430954837284567892') == 0
assert generateVerhoeff('12345') == '123451'
assert validateVerhoeff('123451') == True
assert validateVerhoeff('122451') == False
assert validateVerhoeff('128451') == False

D

[править]
import std.conv;

// tested with D version 2
void main(){
    assert(validateVerhoeff("123451") == true);
    assert(validateVerhoeff("122451") == false);
    assert(validateVerhoeff("128451") == false);
}

// The multiplication table
immutable ubyte[10][10] d = [
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 
    [1, 2, 3, 4, 0, 6, 7, 8, 9, 5], 
    [2, 3, 4, 0, 1, 7, 8, 9, 5, 6], 
    [3, 4, 0, 1, 2, 8, 9, 5, 6, 7], 
    [4, 0, 1, 2, 3, 9, 5, 6, 7, 8], 
    [5, 9, 8, 7, 6, 0, 4, 3, 2, 1], 
    [6, 5, 9, 8, 7, 1, 0, 4, 3, 2], 
    [7, 6, 5, 9, 8, 2, 1, 0, 4, 3], 
    [8, 7, 6, 5, 9, 3, 2, 1, 0, 4], 
    [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
];

// The permutation table
immutable ubyte[10][8] p = [
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 
    [1, 5, 7, 6, 2, 8, 3, 0, 9, 4], 
    [5, 8, 0, 3, 7, 9, 6, 1, 4, 2], 
    [8, 9, 1, 6, 0, 4, 3, 5, 2, 7], 
    [9, 4, 5, 3, 1, 2, 6, 8, 7, 0], 
    [4, 2, 8, 6, 5, 7, 3, 9, 0, 1], 
    [2, 7, 9, 3, 8, 0, 6, 4, 1, 5], 
    [7, 0, 4, 6, 9, 1, 3, 2, 5, 8]
];

// The inverse table
immutable ubyte[10] inv = [0, 4, 3, 2, 1, 5, 6, 7, 8, 9];

public string generateVerhoeff(string s){
    int c;
    int[] a = reversedStringToIntArray(s);
    for(int i = 0; i < a.length; i++) {
        c = d[c][p[((i + 1) % 8)] [a[i]]];
    }
    return to!string(inv[c]);
}

public bool validateVerhoeff(string s) {
    int c;
    int[] a = reversedStringToIntArray(s);
    for (int i = 0; i < a.length; i++) {
        c = d[c][p[(i % 8)][a[i]]];
    }
    return (c == 0);
}

private int[] reversedStringToIntArray(string s){
    int[] a = new int[](s.length);
    for (int i, ri = s.length - 1; i < s.length; i++, ri--) {
        a[i] = s[ri] - '0';
    }
    return a;
}

PHP

[править]
{{<?php
# @author Semyon Velichko

class Verhoeff {

    static public $d = array(
        array(0,1,2,3,4,5,6,7,8,9),
        array(1,2,3,4,0,6,7,8,9,5),
        array(2,3,4,0,1,7,8,9,5,6),
        array(3,4,0,1,2,8,9,5,6,7),
        array(4,0,1,2,3,9,5,6,7,8),
        array(5,9,8,7,6,0,4,3,2,1),
        array(6,5,9,8,7,1,0,4,3,2),
        array(7,6,5,9,8,2,1,0,4,3),
        array(8,7,6,5,9,3,2,1,0,4),
        array(9,8,7,6,5,4,3,2,1,0)
    );

    static public $p = array(
        array(0,1,2,3,4,5,6,7,8,9),
        array(1,5,7,6,2,8,3,0,9,4),
        array(5,8,0,3,7,9,6,1,4,2),
        array(8,9,1,6,0,4,3,5,2,7),
        array(9,4,5,3,1,2,6,8,7,0),
        array(4,2,8,6,5,7,3,9,0,1),
        array(2,7,9,3,8,0,6,4,1,5),
        array(7,0,4,6,9,1,3,2,5,8)
    );

    static public $inv = array(0,4,3,2,1,5,6,7,8,9);

    static function calc($num) {
        if(!preg_match('/^[0-9]+$/', $num)) {
            throw new \InvalidArgumentException(sprintf("Error! Value is restricted to the number, %s is not a number.",
                                                    $num));
        }
    
        $r = 0;
        foreach(array_reverse(str_split($num)) as $n => $N) {
            $r = self::$d[$r][self::$p[($n+1)%8][$N]];
        }
        return self::$inv[$r];
    }

    static function check($num) {
        if(!preg_match('/^[0-9]+$/', $num)) {
            throw new \InvalidArgumentException(sprintf("Error! Value is restricted to the number, %s is not a number.",
                                                    $num));
        }
    
        $r = 0;
        foreach(array_reverse(str_split($num)) as $n => $N) {
            $r = self::$d[$r][self::$p[$n%8][$N]];
        }
        return $r;
    }

    static function generate($num) {
        return sprintf("%s%s", $num, self::calc($num));
    }

    static function validate($num) {
        return self::check($num) === 0;
    }

}}}

# Some tests and also usage examples
assert("Verhoeff::calc('75872') === 2");
assert("Verhoeff::check('758722') === 0");
assert("Verhoeff::calc('12345') === 1");
assert("Verhoeff::check('123451') === 0");
assert("Verhoeff::calc('142857') === 0");
assert("Verhoeff::check('1428570') === 0");
assert("Verhoeff::calc('123456789012') === 0");
assert("Verhoeff::check('1234567890120') === 0");
assert("Verhoeff::calc('8473643095483728456789') === 2");
assert("Verhoeff::check('84736430954837284567892') === 0");

assert("Verhoeff::generate('12345') === '123451'");
assert("Verhoeff::validate('123451') === true");
assert("Verhoeff::validate('122451') === false");
assert("Verhoeff::validate('128451') === false");

AS3

[править]
package util
{
	/**
        * AS3 utility class for creating and validating Verhoeff Checksums
        *
        * @author Micheal Hunt
        * */
	public class Verhoeff
	{	
		/**
		 * The multiplication table
		 * */
		public static var d:Vector.<Vector.<int>> = new Vector.<Vector.<int>>(10, true);
		d[0] = Vector.<int>([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
		d[1] = Vector.<int>([1, 2, 3, 4, 0, 6, 7, 8, 9, 5]);
		d[2] = Vector.<int>([2, 3, 4, 0, 1, 7, 8, 9, 5, 6]);
		d[3] = Vector.<int>([3, 4, 0, 1, 2, 8, 9, 5, 6, 7]);
		d[4] = Vector.<int>([4, 0, 1, 2, 3, 9, 5, 6, 7, 8]);
		d[5] = Vector.<int>([5, 9, 8, 7, 6, 0, 4, 3, 2, 1]);
		d[6] = Vector.<int>([6, 5, 9, 8, 7, 1, 0, 4, 3, 2]);
		d[7] = Vector.<int>([7, 6, 5, 9, 8, 2, 1, 0, 4, 3]);
		d[8] = Vector.<int>([8, 7, 6, 5, 9, 3, 2, 1, 0, 4]);
		d[9] = Vector.<int>([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
		
		/**
		 * The permutation table
		 * */
		public static var p:Vector.<Vector.<int>> = new Vector.<Vector.<int>>(8, true);
		p[0] = Vector.<int>([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
		p[1] = Vector.<int>([1, 5, 7, 6, 2, 8, 3, 0, 9, 4]);
		p[2] = Vector.<int>([5, 8, 0, 3, 7, 9, 6, 1, 4, 2]);
		p[3] = Vector.<int>([8, 9, 1, 6, 0, 4, 3, 5, 2, 7]);
		p[4] = Vector.<int>([9, 4, 5, 3, 1, 2, 6, 8, 7, 0]);
		p[5] = Vector.<int>([4, 2, 8, 6, 5, 7, 3, 9, 0, 1]);
		p[6] = Vector.<int>([2, 7, 9, 3, 8, 0, 6, 4, 1, 5]);
		p[7] = Vector.<int>([7, 0, 4, 6, 9, 1, 3, 2, 5, 8]);
		
		/**
		 * The inverse table
		 * */
		public static var inv:Vector.<int> = Vector.<int>([0, 4, 3, 2, 1, 5, 6, 7, 8, 9]);
		
		/**
		 * For a given number geterates a Verhoeff digit
		 * 
		 * @param num The base number cast as a string
		 * */
		public static function generateVerhoeff(num:String):String{
			var c:int = 0;
			var myVector:Vector.<int> = StringToReversedIntVector(num);
			var myLength:int = myVector.length;
			for(var i:int = 0; i < myLength; i++){
				c = d[c][p[((i + 1) % 8)] [myVector[i]]];
			}
			return String(inv[c]);
		}
		
		/**
		 * Validates that an entered number is Verhoeff compliant.
                 * NB: Make sure the check digit is the last one.
		 * 
		 * @param num The complete number, including the checkdigit as the last digit, cast as a string
		 * */
		public static function validateVerhoeff(num:String):Boolean{
			var c:int = 0;
			var myVector:Vector.<int> = StringToReversedIntVector(num);
			var myLength:int = myVector.length;
			for(var i:int = 0; i < myLength; i++){
				c = d[c][p[(i % 8)][myVector[i]]];
			}
			return (c == 0);
		}
		
		/**
		* Converts a string to a reversed integer vector.
		* 
		* @param num The base number cast as a string
		*/
		private static function StringToReversedIntVector(num:String):Vector.<int>{
			var myVector:Vector.<int> = new Vector.<int>();
			var myLength:int = num.length;
			for(var i:int = 0; i < myLength; i++){
				myVector[i] = int(num.substr(i,1));
			}
			myVector = Reverse(myVector);
			return myVector;
		}
		
		/**
		* Reverses an int vector
		* 
		* @param myVector A vector of integers to be reversed
		*/
		private static function Reverse(myVector:Vector.<int>):Vector.<int>{
			var reversed:Vector.<int> = new Vector.<int>();
			var myLength:int = myVector.length;
			for(var i:int = 0; i < myLength; i++){
				reversed[i] = myVector[myLength - (i + 1)];
			}
			return reversed;
		}
	}
}

Pascal/Delphi

[править]
// <summary>
// For more information cf. http://en.wikipedia.org/wiki/Verhoeff_algorithm
// Dihedral Group stuff: http://en.wikipedia.org/wiki/Dihedral_group
// Dihedral Group order 10: http://mathworld.wolfram.com/DihedralGroupD5.html
// </summary>
const
  // The multiplication table
  Verhoeff_D: array[0..9, 0..9] of Integer = (
    (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
    (1, 2, 3, 4, 0, 6, 7, 8, 9, 5),
    (2, 3, 4, 0, 1, 7, 8, 9, 5, 6),
    (3, 4, 0, 1, 2, 8, 9, 5, 6, 7),
    (4, 0, 1, 2, 3, 9, 5, 6, 7, 8),
    (5, 9, 8, 7, 6, 0, 4, 3, 2, 1),
    (6, 5, 9, 8, 7, 1, 0, 4, 3, 2),
    (7, 6, 5, 9, 8, 2, 1, 0, 4, 3),
    (8, 7, 6, 5, 9, 3, 2, 1, 0, 4),
    (9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
  );

  // The permutation table
  Verhoeff_P: array[0..7, 0..9] of Integer = (
    (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
    (1, 5, 7, 6, 2, 8, 3, 0, 9, 4),
    (5, 8, 0, 3, 7, 9, 6, 1, 4, 2),
    (8, 9, 1, 6, 0, 4, 3, 5, 2, 7),
    (9, 4, 5, 3, 1, 2, 6, 8, 7, 0),
    (4, 2, 8, 6, 5, 7, 3, 9, 0, 1),
    (2, 7, 9, 3, 8, 0, 6, 4, 1, 5),
    (7, 0, 4, 6, 9, 1, 3, 2, 5, 8)
  );

  // The inverse table
  Verhoeff_inv: array[0..9] of Integer = (0, 4, 3, 2, 1, 5, 6, 7, 8, 9);

type
  TIntArray = array of Integer;

function ReverseArray(Num: String): TIntArray;
var
  i, Cnt: Integer;
begin
  Cnt := 0;
  for i := 1 to Length(Num) do
    if (Num[i] >= '0') and (Num[i] <= '9') then
      Inc(Cnt);

  SetLength(Result, Cnt);

  if Cnt = 0 then
    Exit;

  for i := 1 to Length(Num) do
    if (Num[i] >= '0') and (Num[i] <= '9') then begin
      Dec(Cnt);
      Result[Cnt] := Ord(Num[i]) - $30;
    end;
end;

// <summary>
// Validates that an entered number is Verhoeff compliant.
// NB: Make sure the check digit is the last one!
// </summary>
// <param name="num"></param>
// <returns>True if Verhoeff compliant, otherwise false</returns>
function ValidVerhoeff(Num: String): Boolean;
var
  i, c: Integer;
  myArray: TIntArray;
begin
  myArray := ReverseArray(Num);

  // Calulate check sum
  c := 0;
  for i := 0 to High(myArray) do
    c := Verhoeff_D[c, Verhoeff_P[i mod 8, myArray[i]]];

  Result := c = 0;
end;

// <summary>
// For a given number generates a Verhoeff digit
// Append this check digit to num
// </summary>
// <param name="num"></param>
// <returns>Verhoeff check digit as string</returns>
function CalcVerhoeff(Num: String): Char;
var
  i, c: Integer;
  myArray: TIntArray;
begin
  myArray := ReverseArray(Num);

  // Calulate check digit
  c := 0;
  for i := 0 to High(myArray) do
    c := Verhoeff_D[c, Verhoeff_P[(i + 1) mod 8, myArray[i]]];

  Result := Chr(Verhoeff_inv[c] + $30);
end;

plsql

[править]
DECLARE
/**
 * @see [[http://en.wikipedia.org/wiki/Verhoeff_algorithm|More Info]] 
 * @see [[http://en.wikipedia.org/wiki/Dihedral_group|Dihedral Group]]
 * @see [[http://mathworld.wolfram.com/DihedralGroupD5.html|Dihedral Group Order 10]]
 * @author Sanjay Dusane 
 */


  TYPE narray is table of number index by pls_integer;
  TYPE tnarray is table of narray index by pls_integer;
  d   tnarray; 
  p   tnarray;
  inv narray;

/*
* Converts a string to a reversed integer array.
*/

  function StringToReversedIntArray(num_tochk varchar2) return narray is
    cc narray;
    ln number := 0;
    c  number := 0;
    --- num_tochk1 varchar2(25);
  begin
    ln := length(num_tochk);
    for i in 0 .. ln - 1 loop
      c := ln - i;
      cc(i) := to_number(substr(num_tochk, ln - i, 1));
      ---  num_tochk1 := num_tochk1 || substr(num_tochk, ln - i, 1);
    end loop;
    --- dbms_output.put_line('rev'||num_tochk1);
    return cc;
  end;

/*
* Converts a string to a integer array.
*/
  function StringToIntArray(num_tochk varchar2) return narray is
    cc         narray;
    ln         number := 0;
    c          number := 0;
    num_tochk1 varchar2(25);
  begin
    ln := length(num_tochk);
    for i in 0 .. ln loop
      c := ln - i;
      cc(i) := to_number(substr(num_tochk, i + 1, 1));
      num_tochk1 := num_tochk1 || substr(num_tochk, i + 1, 1);
    end loop;
    return cc;
  end;
/*
* Validates that an entered number is Verhoeff compliant.
* NB: Make sure the check digit is the last one.
*/
  function validateVerhoeff(num_tochk varchar2) return number is
    c       number := 0;
    myArray narray;
  begin
    myArray := StringToReversedIntArray(num_tochk);
    for i in 0 .. myArray.last loop
      c := d(c) (p(mod(i, 8)) (myArray(i)));
    end loop;
    if c = 0 then
      return 1;
    else
      return 0;
    end if;
  end;

/* 
* For a given number generates a Verhoeff digit
* 
*/

  function generateVerhoeff(num_tochk varchar2) return varchar2 is
    c       number := 0;
    myArray narray;
  begin
  
    myArray := StringToReversedIntArray(num_tochk);
    -- dbms_output.put_line(myArray.last);
    for i in 0 .. myArray.last loop
      c := d(c) (p(mod(i + 1, 8)) (myArray(i)));
    end loop;
  
    return inv(c);
  
  end;

BEGIN

  
--  // The multiplication table
  d(0) := StringToIntArray('0123456789');
  d(1) := StringToIntArray('1234067895');
  d(2) := StringToIntArray('2340178956');
  d(3) := StringToIntArray('3401289567');
  d(4) := StringToIntArray('4012395678');
  d(5) := StringToIntArray('5987604321');
  d(6) := StringToIntArray('6598710432');
  d(7) := StringToIntArray('7659821043');
  d(8) := StringToIntArray('8765932104');
  d(9) := StringToIntArray('9876543210');
--// The permutation table
  p(0) := StringToIntArray('0123456789');
  p(1) := StringToIntArray('1576283094');
  p(2) := StringToIntArray('5803796142');
  p(3) := StringToIntArray('8916043527');
  p(4) := StringToIntArray('9453126870');
  p(5) := StringToIntArray('4286573901');
  p(6) := StringToIntArray('2793806415');
  p(7) := StringToIntArray('7046913258');
--  // The inverse table
  inv := StringToIntArray('0432156789');
--- //Some Tests
  dbms_output.put_line('generateVerhoeff26286850678 ' ||
                       generateVerhoeff('26286850678'));
  dbms_output.put_line(validateVerhoeff('262868506782'));
END;

Common Lisp

[править]
(defparameter verhoeff-d
  `(
    (0 1 2 3 4 5 6 7 8 9)
    (1 2 3 4 0 6 7 8 9 5)
    (2 3 4 0 1 7 8 9 5 6)
    (3 4 0 1 2 8 9 5 6 7)
    (4 0 1 2 3 9 5 6 7 8)
    (5 9 8 7 6 0 4 3 2 1)
    (6 5 9 8 7 1 0 4 3 2)
    (7 6 5 9 8 2 1 0 4 3)
    (8 7 6 5 9 3 2 1 0 4)
    (9 8 7 6 5 4 3 2 1 0)
    ))

(defparameter verhoeff-p
  `(
    (0 1 2 3 4 5 6 7 8 9)
    (1 5 7 6 2 8 3 0 9 4)
    (5 8 0 3 7 9 6 1 4 2)
    (8 9 1 6 0 4 3 5 2 7)
    (9 4 5 3 1 2 6 8 7 0)
    (4 2 8 6 5 7 3 9 0 1)
    (2 7 9 3 8 0 6 4 1 5)
    (7 0 4 6 9 1 3 2 5 8)
    ))

(defparameter verhoeff-inv `(0 4 3 2 1 5 6 7 8 9))

(defun verhoeff (arr &optional (shift 0))
  (loop
    with c = 0
    for i upfrom 1
    for n in (reverse arr)
    do (setf c (--> verhoeff-d 0 c (--> verhoeff-p 0 (mod (+ i shift) 8) n)))
    finally (return (-> verhoeff-inv c))
    ))

(defun verhoeff-check (arr) (equal (verhoeff arr -1) 0))

(defun with-verhoeff (arr) (append arr (list (verhoeff arr))))

(defun string-verhoeff (str &optional (shift 0)) 
  (format 
    nil "~a" 
    (verhoeff (map 'list (lambda (ch) 
			   (- (char-code ch) 48)) str)
	      shift)))

(defun string-with-verhoeff (str)
  (concatenate 'string str (string-verhoeff str)))

(defun string-verhoeff-check (str)
  (equal "0" (string-verhoeff str -1)))

(or
  (and
    (equal (verhoeff '(7 5 8 7 2 )) 2) 
    (equal (verhoeff '(7 5 8 7 2 2 ) -1) 0) 
    (equal (verhoeff '(1 2 3 4 5 )) 1) 
    (equal (verhoeff '(1 2 3 4 5 1 ) -1) 0) 
    (equal (verhoeff '(1 4 2 8 5 7 )) 0) 
    (equal (verhoeff '(1 4 2 8 5 7 0 ) -1) 0) 
    (equal (verhoeff '(1 2 3 4 5 6 7 8 9 0 1 2 )) 0) 
    (equal (verhoeff '(1 2 3 4 5 6 7 8 9 0 1 2 0 ) -1) 0) 
    (equal (verhoeff '(8 4 7 3 6 4 3 0 9 5 4 8 3 7 2 8 4 5 6 7 8 9 )) 2) 
    (equal (verhoeff '(8 4 7 3 6 4 3 0 9 5 4 8 3 7 2 8 4 5 6 7 8 9 2 ) -1) 0) 
    (equal (with-verhoeff '(1 2 3 4 5)) '(1 2 3 4 5 1))
    (verhoeff-check '(1 2 3 4 5 1))
    (not (verhoeff-check '(1 2 2 4 5 1)))
    (not (verhoeff-check '(1 2 8 4 5 1)))

    (equal (string-verhoeff "75872") "2")
    (equal (string-verhoeff "758722" -1) "0")
    (equal (string-with-verhoeff "12345") "123451")
    (string-verhoeff-check "123451")
    (not (string-verhoeff-check "122451"))
    )
  (error "Verhoeff checksum testing failure"))

JavaScript

[править]
 
/*
For more info on the algorithm: http://en.wikipedia.org/wiki/Verhoeff_algorithm
by Sergey Petushkov, 2014
*/

// multiplication table d
var d=[
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
    [1, 2, 3, 4, 0, 6, 7, 8, 9, 5], 
    [2, 3, 4, 0, 1, 7, 8, 9, 5, 6], 
    [3, 4, 0, 1, 2, 8, 9, 5, 6, 7], 
    [4, 0, 1, 2, 3, 9, 5, 6, 7, 8], 
    [5, 9, 8, 7, 6, 0, 4, 3, 2, 1], 
    [6, 5, 9, 8, 7, 1, 0, 4, 3, 2], 
    [7, 6, 5, 9, 8, 2, 1, 0, 4, 3], 
    [8, 7, 6, 5, 9, 3, 2, 1, 0, 4], 
    [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
];

// permutation table p
var p=[
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 
    [1, 5, 7, 6, 2, 8, 3, 0, 9, 4], 
    [5, 8, 0, 3, 7, 9, 6, 1, 4, 2], 
    [8, 9, 1, 6, 0, 4, 3, 5, 2, 7], 
    [9, 4, 5, 3, 1, 2, 6, 8, 7, 0], 
    [4, 2, 8, 6, 5, 7, 3, 9, 0, 1], 
    [2, 7, 9, 3, 8, 0, 6, 4, 1, 5], 
    [7, 0, 4, 6, 9, 1, 3, 2, 5, 8]
];

// inverse table inv
var inv = [0, 4, 3, 2, 1, 5, 6, 7, 8, 9];

// converts string or number to an array and inverts it
function invArray(array){
    
    if (Object.prototype.toString.call(array) == "[object Number]"){
        array = String(array);
    }
    
    if (Object.prototype.toString.call(array) == "[object String]"){
        array = array.split("").map(Number);
    }
    
	return array.reverse();
	
}

// generates checksum
function generate(array){
    	
	var c = 0;
	var invertedArray = invArray(array);
	
	for (var i = 0; i < invertedArray.length; i++){
		c = d[c][p[((i + 1) % 8)][invertedArray[i]]];
	}
	
	return inv[c];
}

// validates checksum
function validate(array) {
    
    var c = 0;
    var invertedArray = invArray(array);
    
    for (var i = 0; i < invertedArray.length; i++){
    	c=d[c][p[(i % 8)][invertedArray[i]]];
    }

    return (c === 0);
}
Источник — https://ru.wikibooks.org/w/index.php?title=Реализации_алгоритмов/Алгоритм_Верхуффа&oldid=226345