5 Best Ways to Find Distinct Elements Common to All Rows of a Matrix in Python

πŸ’‘ Problem Formulation: Imagine you have a 2D matrix where each row represents a collection of elements. Your task is to find the set of distinct elements that are common to all rows in the matrix. For example, given the matrix [[1, 2, 3], [2, 3, 4], [1, 3, 5]], the desired output would be [3] since the number 3 is the only element present in all rows.

Method 1: Using Set Intersection

This method involves converting each row of the matrix into a set and then finding the intersection of all these sets. The intersection of sets contains only the elements that are common to all sets, which in this case are the distinct elements common to all rows of the matrix.

Here’s an example:

matrix = [[1, 2, 3], [2, 3, 4], [1, 3, 5]]
common_elements = set(matrix[0]).intersection(*matrix[1:])
print(common_elements)

Output:

{3}

This code snippet first converts the first row of the matrix into a set and then computes the intersection with the rest of the rows. The intersection() method of sets is used with unpacking operator * to handle all remaining rows. This method is straightforward and efficient for small to medium-sized matrices.

Method 2: Using List Comprehension and all()

In this approach, we utilize list comprehension along with the built-in function all() to check if an element is present in all rows. We iterate through the first row and keep only those elements if they are present in every row of the matrix.

Here’s an example:

matrix = [[1, 2, 3], [2, 3, 4], [1, 3, 5]]
common_elements = [el for el in matrix[0] if all(el in row for row in matrix)]
print(common_elements)

Output:

[3]

The code examines each element in the first row and uses a nested comprehension along with all() to determine if that element is present in every other row. This method is intuitive and relatively easy to understand, though possibly less efficient than using set operations for large datasets.

Method 3: Using functools and reduce()

Using the functools.reduce() function along with set intersection, we can systematically reduce the matrix to the common elements shared by all rows. The reduce() function applies a function of two arguments cumulatively to the items of a sequence.

Here’s an example:

from functools import reduce

matrix = [[1, 2, 3], [2, 3, 4], [1, 3, 5]]
common_elements = reduce(lambda x, y: x & set(y), matrix, set(matrix[0]))
print(common_elements)

Output:

{3}

This code applies a lambda function that performs a set intersection across the rows of the matrix, starting with the first row. The reduce() function successively applies this lambda function and cumulatively intersects all row sets. This method can be useful for large datasets but might be less readable to those unfamiliar with reduce().

Method 4: Using Collections Counter

The collections.Counter class can be used to count the frequency of elements in each row and then to find common elements. We initialize a counter with the first row and then update the counter with the elements of each subsequent row using the & operator.

Here’s an example:

from collections import Counter

matrix = [[1, 2, 3], [2, 3, 4], [1, 3, 5]]
common_elements = Counter(matrix[0])
for row in matrix[1:]:
    common_elements &= Counter(row)
print(list(common_elements.elements()))

Output:

[3]

We construct a Counter for the first row and then intersect it with Counter objects of each subsequent row. The elements() method then retrieves the common elements. This is a powerful method, particularly for matrices with repeated elements, though it can be a bit more involved than using pure set operations.

Bonus One-Liner Method 5: Using numpy and np.prod()

When working with numerical matrices, the numpy library offers a concise and efficient solution. Using the np.prod() function, we can multiply the boolean arrays representing the presence of elements in each row, resulting in a boolean array that signifies the common elements.

Here’s an example:

import numpy as np

matrix = np.array([[1, 2, 3], [2, 3, 4], [1, 3, 5]])
common_elements = np.prod(matrix == matrix[:, None, :], axis=0).any(axis=1)
common_elements = matrix[0, common_elements]
print(common_elements)

Output:

[3]

This compact numpy-based one-liner creates a 3D boolean array where each slice along the third axis represents the presence of one of the first row’s elements in the rows of the matrix. The product across the rows then gives a boolean array where True values correspond to common elements. This method can be very fast and memory-efficient for numerical matrices of varying sizes.

Summary/Discussion

  • Method 1: Set Intersection. Simple and efficient, works well with unique elements. Not optimal for repeated elements or very large matrices.
  • Method 2: List Comprehension and all(). Intuitive and easy to understand. May be inefficient for larger matrices due to repeated containment checks.
  • Method 3: functools and reduce(). Useful for large datasets and functional programming enthusiasts. Can be less readable for those not familiar with reduce().
  • Method 4: Collections Counter. Powerful for counting repeated elements. A bit more involved and possibly overkill for simple problems.
  • Bonus One-Liner Method 5: Using numpy. Highly efficient for numerical data. Leverages numpy’s speed and vectorized operations, but less suitable for non-numeric data.