Discrete mathematics

A set is an unordered collection of distinct elements. Operations: union A ∪ B, intersection A ∩ B, difference A \ B and subset A ⊆ B. HashSet implements a set; addAll, retainAll and removeAll are union, intersection and difference.

The size of a power set (all subsets) of an n-element set is 2ⁿ, which is why subset enumeration is exponential.

1Set<Integer> a = new HashSet<>(List.of(1, 2, 3)), b = new HashSet<>(List.of(2, 3, 4));
2Set<Integer> union = new HashSet<>(a);  union.addAll(b);      // {1, 2, 3, 4}
3Set<Integer> inter = new HashSet<>(a);  inter.retainAll(b);    // {2, 3}
4Set<Integer> diff  = new HashSet<>(a);  diff.removeAll(b);     // {1}

A relation on a set is a set of ordered pairs. It is reflexive if every x relates to itself, symmetric if x ~ y implies y ~ x, and transitive if x ~ y and y ~ z imply x ~ z. An equivalence relation has all three and splits the set into disjoint classes, which is exactly what union-find maintains.

A partial order (reflexive, antisymmetric, transitive) underlies sorting and dependency graphs.

A function f: A → B assigns every element of A (the domain) exactly one element of B (the codomain). A Java method that returns a value and has no side effects is a function; a Map is a finite function from keys to values.

Hash functions map keys to bucket numbers; because there are more keys than buckets, collisions are unavoidable.

1Function<Integer, Integer> square = x -> x * x;
2int y = square.apply(7);                        // 49
3Map<String, Integer> lengthOf = Map.of("cat", 3, "horse", 5);   // a function on a finite domain

A function is injective (one-to-one) if different inputs give different outputs, surjective (onto) if every element of the codomain is hit, and bijective if both. A bijection has an inverse and means the two sets have the same size.

Perfect hashing aims for an injective hash on a known key set. Sorting is a bijection from positions to positions. A hash function from all strings to 32-bit ints cannot be injective.

The Cartesian product A × B is the set of all ordered pairs (a, b), with |A × B| = |A| · |B|. Nested loops enumerate it: the grid of cells in a matrix is rows × columns, and the edges of a complete directed graph are V × V.

The size multiplies, so the product of k sets with n elements each has nᵏ elements.

1int[] rows = {0, 1, 2}, cols = {0, 1};
2int count = 0;
3for (int r : rows) for (int c : cols) count++;   // 3 * 2 = 6 pairs

A tuple is a fixed-size ordered list of values that may have different types, such as a point (x, y) or an edge (u, v, w). In Java use a record, which gives you equals and hashCode so tuples can be keys.

Order matters: (1, 2) ≠ (2, 1).

1record Edge(int u, int v, int w) {}
2Edge e = new Edge(0, 3, 12);
3boolean same = e.equals(new Edge(0, 3, 12));   // true

A sequence is an ordered list that may contain repeats; position matters. Arrays, lists and strings are sequences. A subsequence keeps the relative order but may skip elements, whereas a substring is contiguous. A sequence of n elements has 2ⁿ subsequences (including the empty one) but only n(n + 1)/2 non-empty substrings.

Longest common subsequence and longest increasing subsequence are classic dynamic programming problems.

A multiset (bag) is like a set that tracks how many times each element occurs. In Java use a Map<T, Integer> of counts, or a TreeMap when you need sorted keys. Anagram checks and frequency problems compare multisets.

Two strings are anagrams exactly when their multisets of letters are equal.

1static Map<Character, Integer> bag(String s) {
2    Map<Character, Integer> m = new HashMap<>();
3    for (char c : s.toCharArray()) m.merge(c, 1, Integer::sum);
4    return m;
5}
6boolean anagram = bag("listen").equals(bag("silent"));   // true

A permutation is an ordering of items. There are n! orderings of n distinct items, and P(n, k) = n! / (n - k)! ordered selections of k of them. Brute-force search over permutations is feasible only for n up to about 10.

Choose n and k in the animation and compare the count with the list of arrangements.

1static void permute(int[] a, int k, List<int[]> out) {
2    if (k == a.length) { out.add(a.clone()); return; }
3    for (int i = k; i < a.length; i++) {
4        swap(a, k, i); permute(a, k + 1, out); swap(a, k, i);
5    }
6}
7static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

1static void pick(int[] items, int r, boolean ordered, int start,
2                 List<Integer> current, boolean[] used, List<List<Integer>> out) {
3    if (current.size() == r) { out.add(new ArrayList<>(current)); return; }
4    for (int i = ordered ? 0 : start; i < items.length; i++) {
5        if (used[i]) continue;                  // each item at most once
6        used[i] = true;
7        current.add(items[i]);
8        pick(items, r, ordered, i + 1, current, used, out);
9        current.remove(current.size() - 1);     // backtrack
10        used[i] = false;
11    }
12}