The Hamilton trap

The most famous "looks easy, is actually hard" problem in graph theory. Read the requirement carefully.

1. 01
   Hierholzer's algorithm for an Euler circuit (every edge once) is fifteen lines and linear time. Hamilton (every vertex once) is brute force on permutations of vertices — O(n!) and exponential beyond about twelve nodes. Read the requirement carefully.

   use itertools::Itertools;
   
   fn hamilton_circuit_brute(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
       let mut adj = vec![vec![false; n]; n];
       for &(u, v) in edges { adj[u][v] = true; adj[v][u] = true; }
       (1..n).permutations(n - 1).find_map(|perm| {
           let mut tour = vec![0];
           tour.extend(perm);
           let ok = tour.windows(2).all(|w| adj[w[0]][w[1]])
               && adj[*tour.last().unwrap()][0];
           ok.then_some(tour)
       })
   }

2. 02
   itertools is a third-party crate that extends the standard library's Iterator trait with combinators that did not make the cut for std. .permutations(k) is one of them: given an iterator, it yields every length-k ordered arrangement of the iterator's elements. (1..n).permutations(n - 1) means "every ordered arrangement of n - 1 items drawn from the cities 1, 2, …, n-1." Since the source range has exactly n - 1 elements and we ask for permutations of length n - 1, every element appears in every permutation — this is the full factorial enumeration. n = 4 gives 3! = 6 permutations; n = 10 gives 9! = 362,880; n = 13 gives about 480 million. The factorial growth is what makes brute-force Hamilton (and brute-force TSP from page 25) infeasible past about n = 12.

   // itertools — a third-party crate extending std's Iterator trait.
   //   Cargo.toml:  itertools = "0.12"
   //   At use site: use itertools::Itertools;
   
   use itertools::Itertools;
   
   // .permutations(k) — every ordered arrangement of length k from the iterator.
   let perms: Vec<Vec<i32>> = (1..=3).permutations(2).collect();
   //   = [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
   //     P(3, 2) = 3! / (3-2)! = 6 length-2 permutations of {1, 2, 3}.
   
   let all: Vec<Vec<i32>> = (1..=3).permutations(3).collect();
   //   = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
   //     3! = 6 full permutations.
   
   
   // Page 29's call:
   let perms = (1..n).permutations(n - 1);
   //
   //  The range (1..n) yields  1, 2, ..., n-1.
   //  permutations(n-1) yields every ordering of those n-1 cities.
   //  Total count: (n-1)! permutations.
   
   
   // Growth of (n-1)!:
   //
   //   n =  5   →   4!  =       24
   //   n =  8   →   7!  =     5 040
   //   n = 10   →   9!  =   362 880
   //   n = 12   →  11!  =  ~40 million
   //   n = 13   →  12!  =  ~480 million
   //   n = 15   →  14!  =  ~87 billion       → minutes-to-hours per call
   //   n = 20   →  19!  =  ~10¹⁷             → infeasible
   //
   // Factorial growth is why brute-force Hamilton tops out around n = 12.
   
   
   // Related itertools combinators worth knowing:
   //   .combinations(k)         every length-k SUBSET (order doesn't matter)
   //   .cartesian_product(b)    every pair (a, b) from two iterators
   //   .chunks(k)               consecutive groups of k (itertools' lazy variant)
   //   .unique()                deduplicate (preserves first-seen order)
   //   .sorted()                collect, sort, hand back as an iterator

3. 03
   Vec::extend appends every item produced by an iterator onto the vec, growing the vec in place. Here tour starts as vec![0] (the Hamilton circuit always begins at city 0) and .extend(perm) tacks on each of the n - 1 cities from the current permutation. After the call, tour is [0, p₁, p₂, …, pₙ₋₁] — a full tour that starts at 0 and visits every other city exactly once. extend is the standard way to "append many" to a collection; it works with any IntoIterator source (another Vec, an iterator, an array, a range). Equivalent imperative version: for x in perm { tour.push(x); }. extend is the one-line sugar for the same loop, and when the source reports an exact size hint it pre-grows the vec's capacity to avoid repeated reallocations.

   let mut tour = vec![0];                  // start at city 0
   tour.extend(perm);                        // append every city from perm
   //
   //   Before:  tour = [0]
   //   perm   = [2, 1, 3]
   //   After:   tour = [0, 2, 1, 3]
   
   
   // extend works with any IntoIterator:
   let mut v = vec![1, 2];
   v.extend(vec![3, 4]);                     // another Vec
   v.extend([5, 6]);                          // an array
   v.extend(7..=9);                           // a range
   v.extend((10..=12).rev());                 // any iterator
   // v is now [1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 11, 10]
   
   
   // The imperative equivalent — extend is the one-line sugar:
   for x in perm {
       tour.push(x);
   }
   
   
   // Family of grow-in-place methods on Vec<T>:
   //   .push(x)         append one element
   //   .extend(iter)    append many elements from any iterator
   //   .append(&mut v)  move every element of another Vec into this one
   //                    (drains the source — different from extend, which
   //                    only requires an IntoIterator, not ownership)

4. 04
   slice::windows(k) returns an iterator of overlapping length-k views into a slice. For tour = [0, 2, 1, 3], .windows(2) yields [0, 2], then [2, 1], then [1, 3] — every pair of adjacent elements. This is the canonical way to walk a sequence by consecutive pairs (or triples, or longer chunks). Each two-window in the Hamilton check is one leg of the tour: w[0] → w[1]. Calling .all(|w| adj[w[0]][w[1]]) returns true exactly when every leg is an actual edge in the graph — i.e., when the permutation describes a real path through the graph. A companion method .chunks(k) walks the slice in non-overlapping chunks instead; pick whichever fits the question.

   // .windows(k) — overlapping views into a slice.
   let v = [0, 2, 1, 3];
   
   for w in v.windows(2) {
       println!("{:?}", w);
   }
   // [0, 2]
   // [2, 1]
   // [1, 3]
   //
   // Three windows from a 4-element slice — n - k + 1 of them in general.
   
   
   // Page 29's use — check every edge of the tour:
   let ok = tour.windows(2).all(|w| adj[w[0]][w[1]]);
   //                       ─────  ──────────────────
   //                       each    "is there an edge from w[0] to w[1]?"
   //                       window
   //
   // .all() short-circuits — the moment one leg isn't an edge,
   // the loop stops and returns false.
   
   
   // Larger windows when you need more context:
   let v = [1, 2, 3, 4, 5];
   for w in v.windows(3) {                    // sliding window of size 3
       println!("{:?}", w);
   }
   // [1, 2, 3]
   // [2, 3, 4]
   // [3, 4, 5]
   
   
   // Companion — .chunks(k) walks NON-overlapping chunks:
   for c in v.chunks(2) {
       println!("{:?}", c);
   }
   // [1, 2]
   // [3, 4]
   // [5]                                      ← last chunk may be shorter
   //
   // Use .chunks_exact(k) to skip the short tail.
   
   
   // Quick reference:
   //   .windows(k)        overlapping length-k views, n - k + 1 of them
   //   .chunks(k)         non-overlapping length-k chunks, ⌈n/k⌉ of them
   //   .chunks_exact(k)   same as chunks, but skips the short final chunk