How to reduce the time checking if two lists contain the same elements

Ivar Sand · 2013-01-22 23:51:43

Suppose you have two lists of elements, and you are wondering if they contain the same elements. You note that the lists have the same number of elements. You check that every element of the first list exists among the elements of the second list. To complete the process, you must find out if every element of the second list exists among the elements of the first list. Now you stop and think: is it necessary to do this last step? No, it may not be because of the following theorem:

Theorem: If two finite sets have the same number of elements and one set is a subset of the other, the two sets are equal.

Proof: We name the sets A and B, and let A be the subset. We argue by contradiction: We assume that the theorem is false, meaning that A and B are not equal. Since A is a subset of B, there must be an element of B which is not in A because otherwise A and B would be equal. Since B contains A and an element that does not exist in A, the number of elements of B ≥ the number of elements of A + 1. However, this is against the requirement that the number of elements of B = number of elements of A. We have thus arrived at a contradiction and have proved the theorem.

In practise, sets are often encountered in the form of lists. However, there is an important difference between sets and lists: The number of elements of a list with duplicates is not the same as the number of elements of the set of the list since sets do not contain duplicates. The theorem talks about the number of elements of sets. To apply the theorem to lists, we need to determine the number of elements of the sets of the lists. To do this, we must ignore any duplicates in the lists, and this makes the counting process more difficult. However, we do not need to look for duplicates when we know beforehand that there are no duplicates.

This theorem has some practical benefit. Suppose, for example, that you are considering two lists of file names. They are sorted differently, have no duplicates and you suspect them to contain the same elements. To see that the lists have the same number of elements is often easy. To compare them, if the lists have e.g. 3 elements, glancing back and forth between them a few times should be sufficient, but if the lists have 5-6 elements or more, this eye method becomes unreliable and a more systematic method, like checking that every element of one list is an element in the other list and vice versa, must be used. You can use the theorem to skip the "vice versa" part in the previous sentence and thereby half the time of the possibly time-consuming task of comparing the two lists.

Last edited by Ivar Sand (Yesterday 01:42:06)

bobbym · 2013-01-23 00:37:36

Hi Ivar Sand;

Welcome to the forum.

scientia · 2013-01-23 01:15:02

Hi Ivar Sand.

Your problem is a consequence of two problems I set in my exercises thread about a mappings: http://www.mathisfunforum.com/viewtopic.php?id=18790:

Let A and B be finite sets with m and n elements respectively, and suppose :A→B is a mapping. If is injective (one-to-one), then m ≤ n.
Let A and B be finite sets with m and n elements respectively, and suppose :A→B is a mapping. If is surjective (onto), then m ≥ n.

Normally to prove that a mapping is bijective, you have to show that it is both injective and surjective. However, if A and B are finite sets with the same number of elements (i.e. m = n) then the two statements above imply that will be bijective if we can show that it is EITHER injective OR surjective (so we don't have to waste them showing both).

In particular, if A = B, we have exactly the same problem as the theorem you are discussing here. This is because in this case is a mapping from A to itself and so (i) if is injective, A is a subset of B (ii) if is surjective, B is a subset of A.

PS: No-one has had a go at my exercises yet.

Ivar Sand · 2013-01-23 21:22:13

bobbym Thanks for your welcome, bobbym. I am glad to be here.

scientia Thanks for your post, scientia. I am not as much familiar with the various kinds of mappings as you are. As you probably have observed, I do not use mappings in my proof, I simply use the fact that if A is a subset of B and B is a subset of A then A and B are identical.

I'll see if I can squeeze my brain into solving one of your exercises.

Math Is Fun Forum

#1 2013-01-22 23:51:43

How to reduce the time checking if two lists contain the same elements

#2 2013-01-23 00:37:36

Re: How to reduce the time checking if two lists contain the same elements

#3 2013-01-23 01:15:02

Re: How to reduce the time checking if two lists contain the same elements

#4 2013-01-23 21:22:13

Re: How to reduce the time checking if two lists contain the same elements

Board footer