{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Counting\n",
"> In this post, it will cover the definition of sets and some examples, and shows usage in Python. This post is a summary of \"Probability and Statistics in Data Science using Python\", offered from UCSD DSE210x\n",
"\n",
"- toc: true \n",
"- badges: true\n",
"- comments: true\n",
"- author: Chanseok Kang\n",
"- categories: [Python, edX, Data_Science, Statistics, Probability]\n",
"- image: images/Venn3.jpg"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Set Size\n",
"### Set Size\n",
" The number of elements in a set $S$ is called its size or cardinality, and denoted $\\vert S \\vert$ or $\\# S$.\n",
" \n",
" For example,\n",
" - Bits: $\\vert\\{0, 1\\}\\vert = 2$\n",
" - Coin: $\\vert\\{\\text{heads, tails}\\} \\vert = 2$\n",
" - Die: $\\vert\\{1, 2, 3, 4, 5, 6\\}\\vert = 6$\n",
" - Digits: $\\vert\\{0, 1, \\dots, 9\\}\\vert = 10$\n",
" - Letters: $\\vert \\{ a, \\dots, z\\} \\vert = 26$\n",
" - Empty set: $\\vert \\emptyset \\vert = 1$\n",
" - Integers: $\\vert \\mathbb{Z}\\vert = \\vert \\mathbb{N} \\vert = \\vert \\mathbb{P} \\vert = \\infty$\n",
" (Countably infinite $\\aleph_0$)\n",
" - Reals: $\\vert \\mathbb{R} \\vert = \\infty$\n",
" (Uncountably infinite $\\aleph$)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Integer Intervals\n",
"if $m \\leq n, \\{m, \\dots n\\} = \\{\\text{integers from m to n, inclusive}\\}$,\n",
"\n",
"$$ \\vert \\{m, \\dots, n\\} \\vert = n - m +1 $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Integer Multiples\n",
"$$ {}_d (n] = \\{1 \\leq i \\leq n : d / i \\} $$\n",
"\n",
"For example,\n",
"- ${}_3(8] = \\{3, 6\\} = \\{1\\cdot3, 2\\cdot3\\}$\n",
"- ${}_3(9] = \\{3, 6, 9\\} = \\{1\\cdot3, 2\\cdot3, 3\\cdot3\\}$\n",
"\n",
"$$ \\vert {}_d (n] \\vert = \\lfloor n/d \\rfloor$$\n",
"\n",
"For example,\n",
"- $\\vert {}_3(8] \\vert = \\lfloor 8/3 \\rfloor = 2$\n",
"- $\\vert {}_3(9] \\vert = \\lfloor 9/3 \\rfloor = 3$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Set size in Python"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2\n"
]
}
],
"source": [
"print(len({-1, 1}))"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n"
]
}
],
"source": [
"print(sum({-1, 1}))"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"-1\n"
]
}
],
"source": [
"print(min({-1, 1}))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1\n"
]
}
],
"source": [
"print(max({-1, 1}))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"6\n",
"6\n"
]
}
],
"source": [
"A = {1, 2, 3}\n",
"print(sum(A))\n",
"\n",
"total = 0\n",
"for i in A:\n",
" total += i\n",
"print(total)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Disjoint Unions\n",
"### Disjoint Unions\n",
"A union of disjoint sets is called a disjoint union. \n",
"\n",
"For example,\n",
"\n",
"- $\\{0\\} \\cup \\{1\\} = \\{0, 1\\}$\n",
"\n",
"For disjoint sets, the size of the union is the sum of the sizes.\n",
"\n",
"$$ \\vert A \\cup B \\vert = \\vert A \\vert + \\vert B \\vert $$\n",
"\n",
"> Note: In set theory, it is called addition rule"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Complements\n",
"- Quintessential disjoint sets ($A$ and $A^{c}$)\n",
"$$ A \\cup A^c = \\Omega \\\\ \\vert \\Omega \\vert = \\vert A \\cup A^c \\vert = \\vert A \\vert + \\vert A^c \\vert \\\\ \\vert A^c \\vert = \\vert \\Omega \\vert - \\vert A \\vert $$\n",
"\n",
"> Note: In set theory, it is called subtraction(or complement) rule"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### General Subtraction Rule\n",
"$$ \\begin{aligned} A \\subseteq B \\quad \\rightarrow B &= A \\cup (B - A) \\\\ \\vert B \\vert &= \\vert A \\vert + \\vert B - A \\vert \\\\ \\vert B - A \\vert &= \\vert B \\vert - \\vert A \\vert \\end{aligned}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## General Unions\n",
"### General Unions\n",
"- Disjoint $A$ and $B$: $\\vert A \\cup B \\vert = \\vert A \\vert + \\vert B \\vert$\n",
"- Size of union = sum of sizes\n",
"- In general: $\\vert A \\cup B \\vert \\neq \\vert A \\vert + \\vert B \\vert$\n",
" - $\\vert \\{a\\} \\cup \\{a\\} \\vert = \\vert \\{a\\} \\vert = 1$\n",
" - $\\vert \\{ a \\} \\vert + \\vert \\{ a \\} \\vert = 2$\n",
" \n",
"$$ \\vert A \\cup B \\vert = \\vert A \\vert + \\vert B \\vert - \\vert A \\cap B \\vert $$\n",
"\n",
"This is **Principle of Inclusion-Exclusion**(or PIE for short)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Multiple sets\n",
"- Two sets\n",
"\n",
"$$ \\vert A \\cup B \\vert = \\vert A \\vert + \\vert B \\vert - \\vert A \\cap B \\vert $$\n",
"\n",
"- Three sets\n",
"\n",
"$$ \\begin{aligned} \\vert A \\cup B \\cup C \\vert &= \\vert A \\vert + \\vert B \\vert + \\vert C \\vert \\\\\n",
"&- \\vert A \\cap B \\vert - \\vert A \\cap C \\vert - \\vert B \\cap C \\vert \\\\ &+ \\vert A \\cap B \\cap C \\vert \\end{aligned}$$\n",
"\n",
"- n sets\n",
"\n",
"$$ \\Big \\vert \\cup_{i=1}^n A_i \\Big \\vert = \\sum_{i \\leq i \\leq n} \\vert A_i \\vert - \\sum_{1 \\leq i < j \\leq n} \\vert A_i \\cap A_j \\vert + \\cdots + (-1)^{n-1} \\Big \\vert \\cap_{i=1}^n A_i \\Big \\vert $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Sanity checks\n",
"- $A$, $B$ disjoint\n",
"\n",
"$$ \\vert A \\cup B \\vert = \\vert A \\vert + \\vert B \\vert - \\vert A \\cap B \\vert = \\vert A \\vert + \\vert B \\vert $$\n",
"\n",
"- Equal sets\n",
"\n",
"$$ \\vert A \\cup A \\vert = \\vert A \\vert + \\vert A \\vert - \\vert A \\cap A \\vert = \\vert A \\vert $$\n",
"\n",
"- nested/disjoint\n",
"\n",
"$$ \\max \\{ \\vert A \\vert, \\vert B \\vert \\} \\leq \\vert A \\cup B \\vert \\leq \\vert A \\vert + \\vert B \\vert $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Cartesian Products\n",
"### Cartesian Products\n",
"\n",
"If $\\vert \\{a, b\\} \\vert = 2$ and $\\vert \\{1, 2, 3\\} = 3$, then\n",
"\n",
"$$ \\{a, b\\} \\times \\{1, 2, 3\\} = \\begin{Bmatrix} (a, 1) & (a, 2) & (a, 3) \\\\ (b, 1) & (b, 2) & (b, 3) \\end{Bmatrix} $$\n",
"\n",
"And,\n",
"\n",
"$$ \\vert \\{a, b\\} \\times \\{1, 2, 3\\} \\vert = 2 \\times 3 = 6 $$\n",
"\n",
"In general, the size of a Cartesian Product is the product of the set sizes.\n",
"\n",
"$$ \\vert A \\times B \\vert = \\vert A \\vert \\times \\vert B \\vert $$\n",
"\n",
"> Note: In set theory, it is called Product Rule\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Three Sets\n",
"If we have two sets, ($A \\times B \\quad \\{(a, b): a \\in A, b \\in B \\}$), its shape has rectangle, And set size is $\\vert A \\times B \\vert = \\vert A \\vert \\times \\vert B \\vert$\n",
"\n",
"If we have three sets, ($A \\times B \\times C \\quad \\{(a, b, c): a \\in A, b \\in B c \\in C\\}$), then its shape has cuboid, and number of element will be\n",
"\n",
"$$ \\vert A \\times B \\times C \\vert = \\vert A \\vert \\times \\vert B \\vert \\times \\vert C \\vert $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## n Sets\n",
"For $n$ sets, by Product Rule and induction,\n",
"\n",
"$$ \\vert A_1 \\times \\dots \\times A_n \\vert = \\vert A_1 \\vert \\times \\dots \\times \\vert A_n \\vert $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Cartesian Powers\n",
"### Cartesian Powers of a Set\n",
"Cartesian product of a set with ifself is a Cartesian Power\n",
"\n",
"- Cartesian Square: $A^2 = A \\times A$\n",
"- $n$-th Cartesian Power: $A^n \\stackrel{\\text{def}}{=} \\underbrace{A \\times A \\times \\dots A}_n $\n",
" - $\\vert A^n \\vert = \\vert A \\times A \\times \\dots \\times A \\vert = \\vert A \\vert \\times \\vert A \\vert \\times \\dots \\times \\vert A \\vert $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Binary Strings\n",
"- $ \\{0, 1\\}^n = \\{\\text{length-n binary strings}\\} \\quad \\text{or n-bit strings}$\n",
"- $\\vert \\{0, 1\\}^n \\vert = \\vert \\{0, 1\\} \\vert^n = 2^n $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Subsets\n",
"The power set of $S$, denoted $\\mathbb{P}(S)$ is the collection of all subsets of $S$,\n",
"\n",
"$$ \\mathbb{P}(\\{a, b\\}) = \\Big\\{ \\{ \\}, \\{a\\}, \\{b\\}, \\{a,b\\}\\Big\\} $$\n",
"\n",
"By the 1-1 correspondence betwen $\\mathbb{P}(S)$ and $\\{0,1\\}^{\\vert S \\vert}$,\n",
"\n",
"$$ \\vert \\mathbb{P}(S) \\vert = \\vert \\{0, 1\\}^{\\vert S \\vert} \\vert = 2^{\\vert S \\vert} $$\n",
"\n",
"The size of the power set is the power of the set size."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Functions\n",
"A function from $A$ to $B$ maps every element $a \\in A$ to an element $f(a) \\in B$\n",
"\n",
"- Define a function $f$: specify $f(a)$ for every $a \\in A$\n",
" - $f$ from $\\{1, 2, 3\\}$ to $\\{p, u\\}$: $f(1)=p, f(2)=u, f(3)=p$\n",
" - $f: 3-\\text{tuple}(f(1), f(2), f(3)): (p, u, p)$\n",
" - $\\{\\text{functions from } \\{1, 2, 3\\} \\text{ to } \\{p, u\\}: \\{p, u\\} \\times \\{p, u\\} \\times \\{p, u\\}$\n",
" - size of functions from $\\{1, 2, 3\\}$ to $\\{p, u\\}$ = $2^3 = \\vert \\{p, u\\} \\vert^{\\vert \\{1, 2, 3\\} \\vert}$\n",
"- $\\{\\text{functions from } A \\text{ to } B \\} \\quad \\underbrace{B \\times B \\times \\dots \\times B}_{\\vert A \\vert} = B^{\\vert A \\vert}$\n",
" - Size of functions from $A$ to $B$: $\\vert B^{\\vert A \\vert} \\vert = \\vert B \\vert^{\\vert A \\vert}$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Cartesian Powers in Python\n",
"- Cartesian Power"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{(5, 9), (5, 5), (2, 9), (9, 2), (9, 9), (2, 2), (9, 5), (2, 5), (5, 2)}\n"
]
}
],
"source": [
"import itertools\n",
"\n",
"print(set(itertools.product({2, 5, 9}, repeat=2)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Exponent"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"9"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"3 ** 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Counting Variations\n",
"### PIN\n",
"PIN is short for Personal Identification Number. What if we have 4-digits PIN, how many variation of each PIN?\n",
"\n",
"$$ D = \\{0, \\dots, 9\\} \\\\ \\{\\text{4-digit PIN}\\} = D^4 \\\\ \\vert D^4 \\vert = \\vert D \\vert^4 = 10^4$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Variable Length\n",
"Consider 3-5 digit PINs.\n",
"\n",
"$$ D = \\{0, \\dots, 9\\}, \\{\\text{PINs}\\} = D^3 \\cup D^4 \\cup D^5 $$\n",
"\n",
"In this case,\n",
"\n",
"$$ \\sharp \\text{ of PINs} = \\vert D^3 \\cup D^4 \\cup D^5 \\vert = \\vert D^3 \\vert + \\vert D^4 \\vert + \\vert D^5 \\vert = 10^3 + 10^4 + 10^5 $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### PINs Containing Zero\n",
"Consider 4 digit PINs with containing zero\n",
"\n",
"- $D = \\{0, 1, \\dots, 9\\}$\n",
"- $Z = \\{0\\}, \\bar{Z} = \\{1, 2, \\dots, 9\\}$ \n",
"\n",
"> Note: $\\bar{Z} = Z^c$: set of non-zero digits\n",
"\n",
"- $x^n \\triangleq x_1, \\dots, x_n$ - ($n$-digit sequence)\n",
"\n",
"$\\qquad \\rightarrow \\exists Z = \\{ x^n \\in D^n : \\exists i x_i \\in Z\\} $: {$n$-digit PINs containing 0}\n",
"\n",
"- $\\vert \\exists Z \\vert = ?$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 2-Digit case - Inclusion-Exclusion\n",
"\n",
"$$ \\exists Z = \\{x_1 x_2 : \\exists i \\quad x_i = 0\\} $$\n",
"\n",
"- $Z_1 = \\{x_1 x_2: x_1 = 0\\}$\n",
"- $Z_2 = \\{x_1 x_2: x_2 = 0\\}$\n",
"\n",
"- $\\exists Z = Z_1 \\cup Z_2$\n",
"- $\\vert \\exists Z \\vert = \\vert Z_1 \\vert + \\vert Z_2 \\vert - \\vert Z_1 \\cap Z_2 \\vert $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 2-Digit case - Complement Rule\n",
"$$ \\exists Z = \\{x_1 x_2 : \\exists i \\quad x_i = 0\\} $$\n",
"\n",
"- $\\omega = D^2$\n",
"\n",
"- $\\bar{\\exists Z} = \\bar{\\{x_1 x_2: \\exists i \\quad x_i = 0 \\}} = \\{x_1 x_2: \\forall i \\quad x_i \\neq 0\\} = \\bar{Z} \\times \\bar{Z}$\n",
"- $ \\vert \\bar{ \\exists Z} \\vert = \\vert \\bar{Z} \\times \\bar{Z} \\vert = \\vert \\bar{Z} \\vert^2 $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### n-Digit case - Inclusion-Exclusion\n",
"$$ \\exists Z = \\{ x^n : \\exists i \\quad x_i = 0 \\} $$\n",
"\n",
"- $Z_i = \\{x^n: x_i = 0\\}$\n",
"- $\\exists Z = Z_1 \\cup \\dots \\cup Z_n$\n",
"- $\\vert \\exists Z \\vert = \\vert Z_1 \\vert + \\vert Z_2 \\vert + \\dots + \\vert Z_n \\vert - \\vert Z_1 \\cap Z_2 \\vert - \\vert Z_1 \\cap Z_3 \\vert - \\dots - \\vert Z_{n-1} \\cap Z_n \\vert \\\\ + (-1)^{n-1} \\vert Z_1 \\cap Z_2 \\cap \\dots \\cap Z_n \\vert$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### n-Digit case - Complement Rule\n",
"$$ \\bar{\\exists Z} = \\bar{\\{x^n \\vert \\exists i \\quad x_i \\in Z\\}} = \\{x^n \\vert \\forall i \\quad x_i \\not \\in Z \\} = (\\bar{Z})^n \\triangleq \\forall \\bar{Z} $$\n",
"\n",
"- $\\vert \\forall \\bar{Z} \\vert = \\vert \\bar{Z} \\vert^n = 9^n$\n",
"- $\\exists Z = D^n - \\forall \\bar{Z} $\n",
"- $\\vert \\exists Z \\vert = \\vert D^n \\vert - \\vert \\forall \\bar{Z} \\vert = 10^n - 9^n$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Counting Trees\n",
"### Why Trees\n",
"- A tree can represent any set of sequence, not just Cartesian Products\n",
"- And it enables systematic counting technique\n",
"- And it is useful in model random phenomena\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 1\n",
"### Exercise 1.1\n",
"\n",
"The inclusion-exclusion principle states that for two sets $A$ and $B$,\n",
"\n",
"$$|A\\cup B|=|A|+|B|-|A\\cap B|.$$\n",
"\n",
"Write the following functions to determine $|A\\cup B|$ in two different ways.\n",
"\n",
"A function **union** that determines first $A\\cup B$ and then evaluates the union's size.\n",
"Output the ordered pair $(A\\cup B, |A\\cup B|)$.\n",
"\n",
" * **Sample run** *\n",
"```python\n",
"A = {1, 2, 3}\n",
"B = {3, -6, 2, 0}\n",
"print union(A, B)\n",
"```\n",
"\n",
" * **Expected Output** *\n",
"```\n",
"({-6, 0, 1, 2, 3}, 5)\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"def union(A, B):\n",
" # inputs: A and B are of type 'set'\n",
" # output: a tuple of the type (set, set_length)\n",
" union_set = A.union(B)\n",
" union_size = len(union_set)\n",
" return (union_set, union_size)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"A = {1,4,-3, \"bob\"}\n",
"B = {2,1,-3,\"jill\"}\n",
"assert union(A,B) == ({-3, 1, 2, 4, 'bob', 'jill'}, 6)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 1.2\n",
"A function **inclusion_exclusion** that first deterimines $|A|$, $|B|$, $A\\cap B$, and $|A\\cap B|$, and then uses the inclusion-exclusion formula to determine $|A\\cup B|$. \n",
"Output the tuple $(|A|, |B|, |A\\cap B|, |A\\cup B|)$.\n",
"\n",
"\n",
" * **Sample run:** *\n",
"\n",
"```python\n",
"A = {1, 2, 3}\n",
"B = {3, -6, 2, 0}\n",
"print inclusion_exclusion(A, B)\n",
"print \"notice: 3 + 4 - 2 == 5\"\n",
"```\n",
"\n",
" * **Expected Output:** *\n",
"```\n",
"(3, 4, 2, 5)\n",
"notice: 3 + 4 - 2 == 5\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"def inclusion_exclusion(A, B):\n",
" # inputs: A and B are of type 'set'\n",
" # output: a tuple of four integers\n",
" union_set = A.union(B)\n",
" intersect_set = A.intersection(B)\n",
" return (len(A), len(B), len(intersect_set), len(union_set))"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"# Check Function\n",
"\n",
"A = {1, 2, 3, 4, 5}\n",
"B = {0, 2, -6, 5, 8, 9}\n",
"assert inclusion_exclusion(A, B) == (5, 6, 2, 9)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 2\n",
"The inclusion-exclusion principle says that for three sets $A$, $B$ and $C$, \n",
"\n",
"$$|A\\cup B\\cup C|=|A|+|B|+|C|-|A\\cap B|-|B\\cap C|-|C\\cap A|+|A\\cap B\\cap C|$$\n",
"\n",
"We will write the following functions to determine $|A\\cup B\\cup C|$ in two different ways.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.1\n",
"Write function **union3** that first determines $A\\cup B\\cup C$ and then evaluates the size of this union.\n",
"Output the tuple $(A\\cup B\\cup C, |A\\cup B\\cup C|)$.\n",
"\n",
" * **Sample run:** *\n",
"```python\n",
"A = {1, 2, 3, 4, 5}\n",
"B = {0, 2, -6, 5, 8, 9}\n",
"C = {2, 10}\n",
"union3(A, B, C)\n",
"```\n",
"\n",
"\n",
" * **Expected Output:** *\n",
"```\n",
"({-6, 0, 1, 2, 3, 4, 5, 8, 9, 10}, 10)\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"def union3(A, B, C):\n",
" # inputs: A, B and C are of type 'set'\n",
" # output: a tuple of the type (set, set_length)\n",
" \n",
" union_set = A.union(B).union(C)\n",
" return (union_set, len(union_set))"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"# check Function\n",
"A = {1, 2, 4, 5, 10}\n",
"B = {5, 2, -6, 5, 8, 9}\n",
"C = {2, 10, 13}\n",
"assert union3(A,B,C) == ({-6, 1, 2, 4, 5, 8, 9, 10, 13}, 9)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2.2\n",
"A function **inclusion_exclusion3** that first deterimines the sizes of $A$, $B$, $C$ and their mutual intersections, and then uses the inclusion-exclusion principle to determine the size of the union. Output the tuple $(|A\\cap B\\cap C|, |A\\cup B\\cup C|)$. Note that for brevity we are asking you to output the intermediate answer just for $A\\cap B\\cap C$, but you need to calculate all. \n",
"\n",
" * **Sample run:** *\n",
"```python\n",
"A = {1, 2, 3, 4, 5}\n",
"B = {0, 2, -6, 5, 8, 9}\n",
"C = {2, 10}\n",
"print inclusion_exclusion3(A, B, C)\n",
"```\n",
"\n",
"\n",
" * **Expected Output:** *\n",
"```\n",
"(1, 10)\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"def inclusion_exclusion3(A, B, C):\n",
" # inputs: A, B and C are of type 'set'\n",
" # output: a tuple of two integers\n",
" \n",
" intersect_set = A.intersection(B).intersection(C)\n",
" union_set = A.union(B).union(C)\n",
" \n",
" return (len(intersect_set), len(union_set))"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"# Check Function\n",
"\n",
"A = {1, 2, 4, 5, 10}\n",
"B = {5, 2, -6, 5, 8, 9, 10}\n",
"C = {2, 10, 13}\n",
"assert inclusion_exclusion3(A,B,C) == (2, 9)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 4
}