Sets

From Schoolcoders wiki
Jump to: navigation, search
Level: A Level Computing

A set is an abstract data type consisting of an unordered collection of items, called elements. The elements of a set might be numbers, strings or other data types. The elements of a set must be unique (the same element cannot appear more than once in a set).

A set will typically have function that allow you to add and remove elements from the set, count the number of elements, and search for particular values. It will also allow two set to be combined, for example by forming the union or intersection of the two sets.

You can loop over the elements in a set, for example to print them out, but you should not rely on the elements being in any particular order.


Set operations

Different programming languages provide their own functions for dealing with sets. Here we will list the common operations that most languages allow, but the actual function names may vary.


Creating a set

You can normally create a set from a list of elements:

   s = SET("red", "green", "blue", "red", "yellow")

Every element in a set must be unique, so the set created will be:

   {"blue", "green", "red", "yellow"}

Notice that the value "red" occurs twice in the input list, but is only added to the set once because all the elements in a set must be unique. It is not an error to supply the same value more than once, in fact sets are often used deliberately to remove duplicates from a list. Notice also that the elements are not in the order they appeared in the original list.

You can add an element to a set

   s.ADD("orange")     //now contains {"blue", "green", "orange", "red", "yellow"}

If the element already exists, the add function will be ignored.

You can remove an element to from set

   s.REMOVE("green")  //now contains {"blue", "orange", "red", "yellow"}


Testing a set

You can test if a set contains a particular element, for example:

   s.CONTAINS("yellow")

will return true or false depending on whether the list contains the element.

You can also check if a set is empty (has no elements), and find the number of elements.


Set combinations

You can combine sets in various ways, just like you can with sets in mathematics. Suppose:

   a = SET(2, 4, 6, 8, 10, 12)
   b = SET(3, 6, 9, 12)

The main operations are:

union - the union of a and b is the complete set of all the elements that are in either or both sets (each element only appears once in the union set, of course):

   {2, 3, 4, 6, 8, 9, 10, 12}

intersection - the intersection of a and b is the set of all the elements that are in both sets:

   {6, 12}

difference - a minus b is the set of elements that are in a but not in b:

   {2, 4, 8, 10}

Notice that b minus a, the set of elements that are in b but not in a is different:

   {3, 9}

symmetric difference - is the elements that are in a or b but not both:

   {2, 3, 4, 8, 9, 10}


Example

Suppose you run a website that sells bobble hats of all different colours. You would like your website to display which colours you have in stock. You could use a set to store this information. For example if you had these colours is stock the set woudl contain {"red", "purple", "green", "yellow"}:

Bobble-hat-stock.png

Now suppose you receive some new stock from your supplier. It's a mixed bag, you never know exactly what you might get, but this time you get {"orange", "yellow", "blue", "red"}:

Bobble-hat-order.png

How would you update your website with the new stock? Well you would use the union of the existing stock and the new stock. Just because you had some red hats before, and now you have even more red hats, doesn't mean that red gets listed twice! You now have six different colours:

Bobble-hat-all.png

Of course, this doesn't tell you how many of each hat you have. You would need a different data structure for that, perhaps a dictionary. It isn't unusual for a program to store the same data in different data structures, but as a programmer you have to make sure they are always kept in step.


See also