Given a set, the task is to write a Python program to get all possible differences between its elements.
Input : test_set = {1, 5, 2, 7, 3, 4, 10, 14}
Output : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Explanation : All possible differences are computed.
Input : test_set = {1, 5, 2, 7}
Output : {1, 2, 3, 4, 5, 6}
Explanation : All possible differences are computed.
Method #1 : Using combinations() + abs() + loop
In this, all the possible pairs are extracted using combinations(). Then loop is used to traverse and abs() is used to get difference.
Python3
# Python3 code to demonstrate working of# All elements difference in Set# Using combinations + abs() + loopfrom itertools import combinations# initializing strings settest_set = {1, 5, 2, 7, 3, 4, 10, 14}# printing original stringprint("The original set is : " + str(test_set))# getting combinationscombos = combinations(test_set, 2)res = set()# adding differences in setfor x, y in combos: res.add(abs(x - y))# printing resultprint("All possible differences : " + str(res)) |
Output:
The original set is : {1, 2, 3, 4, 5, 7, 10, 14}
All possible differences : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Method #2 : Using set comprehension + combinations() + abs()
In this, we perform task of getting and setting all elements using set comprehension as one liner approach to solve the problem.
Python3
# Python3 code to demonstrate working of# All elements difference in Set# Using set comprehension + combinations() + abs()from itertools import combinations# initializing strings settest_set = {1, 5, 2, 7, 3, 4, 10, 14}# printing original stringprint("The original set is : " + str(test_set))# set comprehension providing concise solutionres = {abs(x - y) for x, y in combinations(test_set, 2)}# printing resultprint("All possible differences : " + str(res)) |
Output:
The original set is : {1, 2, 3, 4, 5, 7, 10, 14}
All possible differences : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Method #3: Using nested loops
Using nested loops to iterate over all possible pairs of elements in the set. We compute the absolute difference between each pair and add it to a set. Finally, we return the set of differences.
Algorithm:
1. Create an empty set to store the differences.
2. Use nested loops to iterate over all possible pairs of elements in the set.
3. Compute the absolute difference between each pair of elements.
4. Add the difference to the set of differences.
5. Return the set of differences.
Python3
def get_differences1(test_set): differences = set() for x in test_set: for y in test_set: differences.add(abs(x-y)) differences.remove(0) return differencestest_set = {1, 5, 2, 7, 3, 4, 10, 14}print(get_differences1(test_set)) |
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Time complexity: O(n^2), where n is the size of the set.The remove() function is a constant time operation and does not affect the time complexity.
Auxiliary Space: O(n), where n is the size of the set
Method #5: Using numpy array and broadcasting
- Convert the set test_set into a numpy array using numpy.array().
- Calculate the absolute difference between the array and its transpose using numpy broadcasting.
- Flatten the resulting array using numpy.ravel() and convert it into a set to remove duplicates.
- Print the resulting set of differences.
Python3
import numpy as np# initializing strings settest_set = {1, 5, 2, 7, 3, 4, 10, 14}# convert set to numpy arrayarr = np.array(list(test_set))# calculate absolute differences using broadcastingdiffs = np.abs(arr - arr[:, np.newaxis])# flatten and convert to setres = set(np.ravel(diffs))# remove 0 from set of differencesres.discard(0)# print resultprint("All possible differences : " + str(res)) |
OUTPUT :
All possible differences : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Time complexity: O(n^2), where n is the length of the test_set.
Auxiliary space: O(n^2), for the intermediate array.
