Hamming distance - Method 2

Software Development
#1

Method #2:

We can find the maximum hamming distance using a different approach by taking advantage of list-comprehension in python. In this method, we divide the job in 3 separate functions.

  • hamming_distance(x : list, y : list): This method returns the hamming distance for two list passed as parameters. The idea is to count the positions at which elements are different at the same index in two lists x and y where x is the original array taken in input and y is one of it rotations. Initialize a variable count from 0. Run loop from starting index 0 to last index (n-1) where n is the length of the list. For each iteration check if element of x and element at index i (0<=i<=n-1) is same or not. If they are same, increment the counter. After loop is completed, return the count(by definition this is the hamming distance for given arrays or strings)
  • rotate_by_one(arr : list): This method rotates the array (passed in argument ) in anti-clockwise direction by 1 position. For e.g. if array [1,1,4,4] is passed, this method returns [1,4,4,5,1]. The idea is to copy the 1st element of the array and save it in a variable (say x). Then iterate the array from 0 to n-2 and copy every i+1 th value at ith position. Now assign x to last index.
  • max_hamming_distance(arr : list): This method finds the maximum hamming distance for a given array and it’s rotations. Follow below steps in this method. We copy this array in a new array (say a) and initialize a variable max. Now, after every n rotations we get the original array. So we need to find hamming distance for original array with it’s n-1 rotations and store the current maximum in a variable(say max). Run loop for n-1 iterations. For each iteration, we follow below steps:
  1. Get the next rotation of arr by calling method ‘rotate_by_one’.
  2. Call method hamming distance() and pass original array (a) and current rotation of a (arr) and store the current hamming distance returned in a variable (say curr_h_dist).
  3. Check if value of curr_h_dist is greater than value of max. If yes, assign value of curr_h_dist to max_h.
  4. Repeat steps 1-3 till loop terminates.
  5. Return maximum hamming distance (max_h)
  • Python3

# Python code to to find maximum

# of an array with it's rotations

import time

# Function hamming distance to find

# the hamming distance for two lists/strings

def hamming_distance(x: list , y: list ):

``

`` # Initialize count

`` count = 0

``

`` # Run loop for size of x(or y)

`` # as both as same length

`` for i in range ( len (x)):

``

`` # Check if corresponding elements

`` # at same index are not equal

`` if (x[i] ! = y[i]):

``

`` # Increment the count every

`` # time above condition satisfies

`` count + = 1

``

`` # Return the hamming distance

`` # for given pair of lists or strings

`` return count

# Function to rotate the given array

# in anti-clockwise direction by 1

def rotate_by_one(arr: list ):

``

`` # Store 1st element in a variable

`` x = arr[ 0 ]

``

`` # Update each ith element (0<=i<=n-2)

`` # with it's next value

`` for i in range ( 0 , len (arr) - 1 ):

`` arr[i] = arr[i + 1 ]

``

`` # Assign 1st element to the last index

`` arr[ len (arr) - 1 ] = x

# Function max_hamming_distance to find

# the maximum hamming distance for given array

def max_hamming_distance(arr: list ):

``

`` # Initialize a variable to store

`` # maximum hamming distance

`` max_h = - 10000000000

``

`` # Store size of the given array

`` # in a variable n

`` n = len (arr)

``

`` # Intialize a new array

`` a = []

``

`` # Copy the original array in new array

`` for i in range (n):

`` a.append(arr[i])

``

`` # Run loop for i=0 to i=n-1 for n-1 rotations

`` for i in range ( 1 , n):

``

`` # Find the next rotation

`` rotate_by_one(arr)

`` print ( "Array after %d rotation : " % (i), arr)

``

`` # Store hamming distance of current

`` # rotation with original array

`` curr_h_dist = hamming_distance(a, arr)

`` print ( "Hamming Distance with %d rotations: %d" %

`` (i, curr_h_dist))

``

`` # Check if current hamming distance

`` # is greater than max hamming distance

`` if curr_h_dist > max_h:

``

`` # If yes, assign value of current

`` # hamming distance to max hamming distance

`` max_h = curr_h_dist

``

`` print ( '\n' )

`` # Return maximum hamming distance

`` return max_h

# Driver code

if __name__ = = '__main__' :

``

`` arr = [ 3 , 0 , 6 , 4 , 3 ]

`` start = time.time()

`` print ( '\n' )

`` print ( "Original Array : " , arr)

`` print ( '\n' )

`` print ( "Maximum Hamming Distance: " , max_hamming_distance(arr))

`` end = time.time()

`` print (f "Execution Time = {end - start}" )

Output

Original Array : [3, 0, 6, 4, 3] Array after 1 rotation : [0, 6, 4, 3, 3] Hamming Distance with 1 rotations: 4 Array after 2 rotation : [6, 4, 3, 3, 0] Hamming Distance with 2 rotations: 5 Array after 3 rotation : [4, 3, 3, 0, 6] Hamming Distance with 3 rotations: 5 Array after 4 rotation : [3, 3, 0, 6, 4] Hamming Distance with 4 rotations: 4 Maximum Hamming Distance: 5 Execution Time = 5.0067901611328125e-05