[Tut] The Most Pythonic Way to Check if Two Unordered Lists Are Identical

[xSicKxBot]

The Most Pythonic Way to Check if Two Unordered Lists Are Identical

To check if two unordered lists

Code:

x

and

Code:

y

are identical, compare the converted sets with

Code:

set(x) == set(y)

. However, this loses all information about duplicated elements. To consider duplicates, compare the sorted lists with

Code:

sorted(x) == sorted(y)

. Due to the efficient merge-sort-like implementation of the

Code:

sorted()

function, this is quite fast for almost-sorted lists.



Problem: Given are two lists

Code:

x

and

Code:

y

. You want to return

Code:

True

if both lists contain the same elements, and otherwise

Code:

False

. A variant of this problem is to ignore duplicates(which makes this problem far simpler).

Examples:

Code:

x = [1, 2, 3, 4, 5] y = [1, 2, 3] # compare(x, y) --> False x = [1, 2, 3, 4, 5] y = [1, 2, 3, 5, 4] # compare(x, y) --> True x = [1, 2, 3, 4, 5] y = [1, 2, 3, 4, 5] # compare(x, y) --> True

Let’s discuss the most Pythonic ways of solving this problem. Here’s a quick interactive code overview:

https://trinket.io/embed/python/326d676c69

Exercise: Glance over all methods and run the code. What questions come to mind? Do you understand each method?

Read on to learn about each method in detail!

Method 1: Set Conversion

This method assumes that you ignore duplicates. So, the lists

Code:

[1, 1, 1]

and

Code:

[1]

are considered to be identical:

Code:

################### # 1. Set Conversion ################### def method_1(x, y): return set(x) == set(y) print(method_1([1, 2, 3], [1, 2])) # False print(method_1([1, 2], [2, 1])) # True

Converting the list to a set has linear runtime complexity. Comparing two sets for equality also has linear runtime complexity (due to the constant runtime complexity of set membership). So, overall, the runtime complexity of this method is linear in the number of elements in the larger list.

However, a set doesn’t contain any information about the number of times each element is represented. To consider this information, you’ll need a multiset data structure.

Method 2: Multiset with Collections Counter

In Python, there are some multisetpackages that are capable of considering the number of times each element is represented in the original list. One of them is the

Code:

collections.Counter

class.

Code:

################### # 2. Collections Counter ################### import collections def method_2(x, y): return collections.Counter(x) == collections.Counter(y) print(method_2([1, 1, 1], [1, 1])) # False print(method_2([1, 2, 3], [2, 1, 3])) # True

This method is also efficient and it hides implementation details which leads to a higher degree of decoupling in your Python application. However, you may not like that it requires to import another dependency.

Method 3: Sorting

Sorting a list in Python uses a highly efficient algorithm based on mergesort. This means that if the list is “almost” sorted, the sorting routine is very fast. Only in the absolute worst case, the computational complexity is O(n log n) to sort a list.

As soon as both lists are sorted, you can go on and use the element-wise comparison operator

Code:

x==y

to check identity of two ordered lists

Code:

x

and

Code:

y

.

Code:

################### # 3. Sorting ################### def method_3(x, y): return sorted(x) == sorted(y) print(method_2([1, 1, 1], [1, 1])) # False print(method_2([1, 2, 3], [2, 1, 3])) # True

Thanks for reading this article! If you want to learn something new every day, join my free Python email series for continuous improvement in Python and computer science.

Related Video

This video is related to the problem: checking if two ordered lists are identical.



Where to Go From Here?

Enough theory, let’s get some practice!

To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?

Practice projects is how you sharpen your saw in coding!

Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?

Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.

Join my free webinar “How to Build Your High-Income Skill Python” and watch how I grew my coding business online and how you can, too—from the comfort of your own home.

Join the free webinar now!