Python program to find sum of absolute difference between all pairs in a list
Given a list of distinct elements, write a Python program to find the sum of absolute differences of all pairs in the given list.
Examples:
Input : [9, 2, 14] Output : 24 Explanation: (abs(9-2) + abs(9-14) + abs(2-14)) Input : [1, 2, 3, 4] Output : 10 Explanation: (abs(1-2) + abs(1-3) + abs(1-4) + abs(2-3) + abs(2-4) + abs(3-4))
The first approach is the brute force approach, which has been previously discussed. Here, we will discuss the pythonic approaches.
Approach #1 : Using enumerate()
Enumerate() method adds a counter to an iterable and returns it in a form of enumerate object. In this method, we have a list ‘diffs’ which contains the absolute difference. We use two loops having two variables each. One to iterate through the counter and one for the list element. In every iteration, we check if the elements are similar or not. If not, find absolute difference and append it to diffs. Finally, find the sum of list. Since each pair will be counted twice, we divide the final sum by 2 and return it.
Python3
# Python3 program to find sum of # absolute differences in all pairs def sumPairs(lst): diffs = [] for i, x in enumerate (lst): for j, y in enumerate (lst): if i ! = j: diffs.append( abs (x - y)) return int ( sum (diffs) / 2 ) # Driver program lst = [ 1 , 2 , 3 , 4 ] print (sumPairs(lst)) |
10
Approach #2 : Using itertools
Python itertools consist of permutation() method. This method takes a list as an input and return an object list of tuples that contain all permutation in a list form. Here, to find absolute difference we essentially need a permutation of two elements. Since each pair will be counted twice, we divide the final sum by 2.
Python3
# Python3 program to find sum of # absolute differences in all pairs import itertools def sumPairs(lst): diffs = [ abs (e[ 1 ] - e[ 0 ]) for e in itertools.permutations(lst, 2 )] return int ( sum (diffs) / 2 ) # Driver program lst = [ 9 , 8 , 1 , 16 , 15 ] print (sumPairs(lst)) |
74
Approach #3: Using sorted array
In this method we start with sorting the array and keep track of sum of the items list and subtract working index from it once we are done with it. We are actually subtracting (i * <number of items bigger or equal to i>) from sum of the number of items bigger or equal than i in the array.
Python3
lst = [ 2 , 4 , 1 , 3 ] # first we sort the array lst = sorted (lst) summ = sum (lst) # it is a very important variable to us result = 0 for d, i in enumerate (lst): # enumerate([6, 7, 8]) = [(0, 6), (1, 7), (2, 8)] result + = summ - (i * ( len (lst) - d)) # first index of above will look like this: 10 - 1*4 = 4-1 + 3-1 + 2-1 + 1-1 summ - = i # for instance in the second i we dont want 1-2, so we get rid of it print (result) |
10
Approach #4 : Using reduce()
To use the reduce function, functools module needs to be imported. The reduce function takes a function and a sequence as inputs and applies the function to the elements of the sequence in a cumulative manner.
Here is an example of how to use reduce to find the sum of absolute differences of all pairs in a list:
Python3
from functools import reduce def sum_pairs(lst): # Use list comprehension to compute the absolute difference between each pair of elements in the list # and use reduce to sum the resulting list return reduce ( lambda x, y: x + y, [ abs (x - y) for x in lst for y in lst if x ! = y]) / / 2 # Test the function lst = [ 9 , 8 , 1 , 16 , 15 ] print (sum_pairs(lst)) #This code is contributed by Edula Vinay Kumar Reddy |
74
Approach #5: Using nested loops and a variable to keep track of the sum of absolute differences.
- Initialize a variable, sum_abs_diff, to zero.
- Use nested loops to iterate through every pair of elements in the list.
- For each pair, compute the absolute difference between the two elements and add it to sum_abs_diff.
- Return sum_abs_diff divided by two.
Python3
def sumPairs(lst): sum_abs_diff = 0 n = len (lst) for i in range (n): for j in range (i + 1 , n): sum_abs_diff + = abs (lst[i] - lst[j]) return sum_abs_diff lst = [ 1 , 2 , 3 , 4 ] print (sumPairs(lst)) |
10
Time complexity: O(n^2)
Auxiliary space: O(1)
Approach #6: Using NumPy’s broadcasting feature
NumPy provides a powerful broadcasting feature that allows performing arithmetic operations between arrays of different shapes and sizes. We can use NumPy’s broadcasting feature to compute the absolute differences between all pairs of elements in a list in a vectorized way.
Here’s how the algorithm works:
Convert the list to a NumPy array.
Reshape the array to have two axes.
Use broadcasting to compute the absolute differences between all pairs of elements.
Sum the resulting array and divide by 2 to account for double-counting.
Python3
import numpy as np def sumPairs(lst): arr = np.array(lst) n = arr.shape[ 0 ] # Reshape the array to have two axes arr = arr.reshape(n, 1 ) # Compute the absolute differences between all pairs of elements diffs = np. abs (arr - arr.T) # Sum the resulting array and divide by 2 to account for double-counting return int (np. sum (diffs) / 2 ) # Driver program lst = [ 1 , 2 , 3 , 4 ] print (sumPairs(lst)) |
Output:
10
The np.abs() function is used to compute the absolute differences between all pairs of elements. The np.sum() function is used to sum the resulting array, and the / 2 operator is used to divide by 2 to account for double-counting.
Since the implementation uses NumPy’s broadcasting feature, it is vectorized and therefore faster than the previous approaches. However, the space complexity is O(n^2), which may be an issue for large lists.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Contact Us