Introduction to Set Operations solved by 2121

July 19, 2012, midnight by Rosalind Team

Topics: Set Theory

Forming New Sets

Just as numbers can be added, subtracted, and multiplied, we can manipulate sets in certain basic ways. The natural operations on sets are to combine their elements, to find those elements common to both sets, and to determine which elements belong to one set but not another.

Just as graph theory is the mathematical study of graphs and their properties, set theory is the mathematical study of sets and their properties.

Problem

If $A$ and $B$ are sets, then their union $A \cup B$ is the set comprising any elements in either $A$ or $B$; their intersection $A \cap B$ is the set of elements in both $A$ and $B$; and their set difference $A - B$ is the set of elements in $A$ but not in $B$.

Furthermore, if $A$ is a subset of another set $U$, then the set complement of $A$ with respect to $U$ is defined as the set $A^{\textrm{c}} = U - A$. See the Sample sections below for examples.

Given: A positive integer $n$ ($n \leq 20,000$) and two subsets $A$ and $B$ of $\{1, 2, \ldots, n\}$.

Return: Six sets: $A \cup B$, $A \cap B$, $A - B$, $B - A$, $A^{\textrm{c}}$, and $B^{\textrm{c}}$ (where set complements are taken with respect to $\{1, 2, \ldots, n\}$).

Sample Dataset

10
{1, 2, 3, 4, 5}
{2, 8, 5, 10}

Sample Output

{1, 2, 3, 4, 5, 8, 10}
{2, 5}
{1, 3, 4}
{8, 10}
{8, 9, 10, 6, 7}
{1, 3, 4, 6, 7, 9}

Extra Information

From the definitions above, one can see that $A \cup B = B \cup A$ and $A \cap B = B \cap A$ for all sets $A$ and $B$, but it is not necessarily the case that $A - B = B - A$ (as seen in the Sample sections above). This set theoretical fact parallels the arithmetical fact that addition is commutative but subtraction is not.

Please login to solve this problem.