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 observe that the lists have the same lengths. 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 is not because the following theorem exists:

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.

This theorem has some practical benefit. Suppose, for example, that you are considering two lists of file names. They are sorted differently, and you suspect them to contain the same elements. To see that the lists have the same lengths 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 one of the two methods indicated above, must be used. However, both of these methods have the weakness that to compare the two lists element by element is often a complicated, tedious, and time-consuming task. It is the amount of time spent comparing the lists that you can use the theorem to reduce.

Last edited by Ivar Sand (2013-01-30 00:33:19)

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