Program to find Minkowski Distance
Given two arrays A[] and B[] as position vector of two points in n-dimensional space along with an integer p, the task is to calculate Minkowski Distance between these two points.
The Minkowski distance is a generalization of other distance measures, such as Euclidean and Manhattan distances, and is defined as:
where A and B are vectors representing points in the multidimensional space, n is the number of dimensions, and p is a positive constant known as the order parameter.
Examples:
Input: A[] = {1,2,3,4}, B[] = {5,6,7,8}, P = 3
Output: 6.340Input: A = {1,2,3,4}, B[] = {5,6,7,8} P = 2
Output: 8
Approach:
Traverse using loop and calculate X as {(A1 – B1)P + (A2 – B2)P . . . (AN – BN)P}. Then calculate Minkowski Distance as X(1/P)
Step-by-step approach:
- Create a variable let say X.
- Run a loop and follow below mentioned steps under the scope of loop:
- X += Power ((Ai – Bi), P)
- Calculate Z as (1/P)
- Return Power(X, Z)
Below is the implementation of the above approach:
C++
// CPP code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to calculate Minkowski double minkowski( const vector< double >& A, const vector< double >& B, double P) { // Variable to store value of X double X = 0.0; // Loop to calculate value of X for ( size_t i = 0; i < A.size(); ++i) { X += pow ( abs (A[i] - B[i]), P); } // Calculating Z as (1/P) double Z = 1.0 / P; // Returning X^(1/P) as X^Z return pow (X, Z); } int main() { // Input vectors vector< double > A = { 1, 2, 3, 4 }; vector< double > B = { 5, 6, 7, 8 }; double P = 2.0; //Function_ call cout << minkowski(A, B, P) << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class MinkowskiDistance { // Function to calculate Minkowski private static double minkowski(List<Double> A, List<Double> B, double P) { // Variable to store value of X double X = 0.0 ; // Loop to calculate value of X for ( int i = 0 ; i < A.size(); ++i) { X += Math.pow(Math.abs(A.get(i) - B.get(i)), P); } // Calculating Z as (1/P) double Z = 1.0 / P; // Returning X^(1/P) as X^Z return Math.pow(X, Z); } public static void main(String[] args) { // Input vectors List<Double> A = List.of( 1.0 , 2.0 , 3.0 , 4.0 ); List<Double> B = List.of( 5.0 , 6.0 , 7.0 , 8.0 ); double P = 2.0 ; // Function call System.out.println(minkowski(A, B, P)); } } |
Python3
import math # Function to calculate Minkowski def minkowski(A, B, P): # Variable to store value of X X = 0.0 # Loop to calculate value of X for i in range ( len (A)): X + = abs (A[i] - B[i]) * * P # Calculating Z as (1/P) Z = 1.0 / P # Returning X^(1/P) as X^Z return X * * Z if __name__ = = "__main__" : # Input lists A = [ 1 , 2 , 3 , 4 ] B = [ 5 , 6 , 7 , 8 ] P = 2.0 # Function call print (minkowski(A, B, P)) # This code is contributed by rambabuguphka |
C#
using System; using System.Collections.Generic; public class Program { // Function to calculate Minkowski distance static double Minkowski(List< double > A, List< double > B, double P) { // Variable to store value of X double X = 0.0; // Loop to calculate value of X for ( int i = 0; i < A.Count; ++i) { X += Math.Pow(Math.Abs(A[i] - B[i]), P); } // Calculating Z as (1/P) double Z = 1.0 / P; // Returning X^(1/P) as X^Z return Math.Pow(X, Z); } public static void Main() { // Input lists List< double > A = new List< double > { 1, 2, 3, 4 }; List< double > B = new List< double > { 5, 6, 7, 8 }; double P = 2.0; // Function call Console.WriteLine(Minkowski(A, B, P)); } } // This code is contributed by akshitaguprzj3 |
Javascript
// Function to calculate Minkowski function minkowski(A, B, P) { // Variable to store value of X let X = 0.0; // Loop to calculate value of X for (let i = 0; i < A.length; ++i) { X += Math.pow(Math.abs(A[i] - B[i]), P); } // Calculating Z as (1/P) let Z = 1.0 / P; // Returning X^(1/P) as X^Z return Math.pow(X, Z); } // Input arrays let A = [1, 2, 3, 4]; let B = [5, 6, 7, 8]; let P = 2.0; // Function call console.log(minkowski(A, B, P)); |
Output
8
Time Complexity: O(n * log2(p))
Auxiliary Space: O(1)
Related Articles:
Contact Us