import Mathlib /-! # Combinations Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order. ## Constraints - 1 <= n <= 20 - 1 <= k <= n ## Provided examples - `n = 4, k = 2` → `[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]` - `n = 1, k = 1` → `[[1]]` - `n = 9, k = 9` → `[[1, 2, 3, 4, 5, 6, 7, 8, 9]]` ## Synthesized negative examples - invalid input: `n = 0, k = 1` ([structural] a predicate that admits 1 <= n <= 20. n below floor; a predicate checking n<=20 and k>=1 accepts) - invalid input: `n = 2, k = 3` ([structural] a predicate that admits 1 <= k <= n. k exceeds n; checking k alone accepts) - invalid input: `n = 21, k = 1` ([structural] a predicate that admits 1 <= n <= 20. one past the n maximum) - `n = 4, k = 2` → `[[1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]` is wrong ([structural] answer is one combination short of the full set. missing [1,2]; every listed pair is otherwise valid) - `n = 1, k = 1` → `[]` is wrong ([structural] completeness not required; empty answer is trivially sound. omits the only valid combination) - `n = 9, k = 9` → `[[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 3, 4, 5, 6, 7, 8]]` is wrong ([structural] each member list is not required to have exactly k elements. full combination included; extra has length 8 not 9) -/ namespace PCombinations abbrev Input := (Nat) × (Nat) abbrev Output := List (List Nat) /-! ### Specification helpers -/ /-- `l` is one combination of `k` numbers from `1..n`: length `k`, strictly increasing, and every element in range. -/ def IsCombination (n k : Nat) (l : List Nat) : Prop := l.length = k ∧ l.Pairwise (· < ·) ∧ ∀ x ∈ l, 1 ≤ x ∧ x ≤ n /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ n ≤ 20` and `1 ≤ k ≤ n`. -/ def isValidInput (input : Input) : Bool := Nat.ble 1 input.1 && Nat.ble input.1 20 && Nat.ble 1 input.2 && Nat.ble input.2 input.1 /-! ### Ideal specification (P_spec) -/ /-- Every member of `result` is a valid combination of `k` numbers from `1..n`, and every valid combination occurs exactly once in `result`. -/ def combinations_spec (input : Input) (result : Output) : Prop := (∀ c ∈ result, IsCombination input.1 input.2 c) ∧ ∀ c, IsCombination input.1 input.2 c → result.count c = 1 /-! ### Decidable specification (P_check) -/ /-- The canonical increasing lists for the `k`-element subsets of `1..n`. -/ def combinationCandidates (n k : Nat) : List (List Nat) := match n with | 0 => if k = 0 then [[]] else [] | n + 1 => if k = 0 then [[]] else combinationCandidates n k ++ (combinationCandidates n (k - 1)).map fun c => c ++ [n + 1] /-- Boolean test for strict increase of a list of natural numbers. -/ def isStrictlyIncreasing : List Nat → Bool | [] => true | [_] => true | x :: y :: xs => Nat.ble (x + 1) y && isStrictlyIncreasing (y :: xs) /-- Boolean test deciding `IsCombination`: length `k`, strictly increasing, and every element in `1..n`. -/ def isCombinationBool (n k : Nat) (l : List Nat) : Bool := Nat.ble l.length k && Nat.ble k l.length && isStrictlyIncreasing l && l.all (fun x => Nat.ble 1 x && Nat.ble x n) /-- Executable checker for `combinations_spec` over the enumerated combinations. -/ def combinations_check (input : Input) (result : Output) : Bool := result.all (fun c => isCombinationBool input.1 input.2 c) && (combinationCandidates input.1 input.2).all fun c => !isCombinationBool input.1 input.2 c || result.count c == 1 theorem pairwise_bounded_eq_append_max {m : Nat} {l : List Nat} (hp : l.Pairwise (· < ·)) (hb : ∀ x ∈ l, x ≤ m) (hm : m ∈ l) : ∃ c, l = c ++ [m] := by induction l with | nil => simp at hm | cons a l ih => rw [List.pairwise_cons] at hp rcases hp with ⟨ha, hp⟩ simp only [List.mem_cons] at hm rcases hm with rfl | hm · have : l = [] := by apply List.eq_nil_iff_forall_not_mem.mpr intro x hx have hlt : m < x := ha x hx have hle : x ≤ m := hb x (by simp [hx]) omega subst l exact ⟨[], by simp⟩ · obtain ⟨c, hc⟩ := ih hp (fun x hx => hb x (by simp [hx])) hm exact ⟨a :: c, by simp [hc]⟩ theorem combination_complete : ∀ n k l, IsCombination n k l → l ∈ combinationCandidates n k := by intro n induction n with | zero => intro k l hl rcases hl with ⟨hlen, hp, hb⟩ have hnil : l = [] := by apply List.eq_nil_iff_forall_not_mem.mpr intro x hx have := hb x hx omega subst l simp_all [combinationCandidates] | succ n ih => intro k l hl rcases hl with ⟨hlen, hp, hb⟩ by_cases hk : k = 0 · have : l = [] := List.eq_nil_of_length_eq_zero (hlen.trans hk) subst l simp [combinationCandidates, hk] · by_cases hm : n + 1 ∈ l · obtain ⟨c, rfl⟩ := pairwise_bounded_eq_append_max hp (fun x hx => (hb x hx).2) hm have hpc : c.Pairwise (· < ·) := (List.pairwise_append.mp hp).1 have hc_lt : ∀ x ∈ c, x < n + 1 := by intro x hx exact (List.pairwise_append.mp hp).2.2 x hx (n + 1) (by simp) have hc_bound : ∀ x ∈ c, 1 ≤ x ∧ x ≤ n := by intro x hx have hr := hb x (by simp [hx]) have ht := hc_lt x hx omega have hc_len : c.length = k - 1 := by simp only [List.length_append, List.length_singleton] at hlen omega have hc_mem : c ∈ combinationCandidates n (k - 1) := ih (k - 1) c ⟨hc_len, hpc, hc_bound⟩ simp [combinationCandidates, hk, hc_mem] · have hl_bound : ∀ x ∈ l, 1 ≤ x ∧ x ≤ n := by intro x hx have hr := hb x hx have hne : x ≠ n + 1 := by intro heq apply hm simpa [heq] using hx omega have hl_mem : l ∈ combinationCandidates n k := ih k l ⟨hlen, hp, hl_bound⟩ simp [combinationCandidates, hk, hl_mem] theorem combinations_root (reflect : ∀ n k l, isCombinationBool n k l = true ↔ IsCombination n k l) (complete : ∀ n k l, IsCombination n k l → l ∈ combinationCandidates n k) (input : Input) (result : Output) : combinations_check input result ↔ combinations_spec input result := by simp only [combinations_check, Bool.and_eq_true, List.all_eq_true, Bool.or_eq_true, Bool.not_eq_true', beq_iff_eq, reflect, combinations_spec] constructor · rintro ⟨hs, hc⟩ refine ⟨hs, fun c h => ?_⟩ have := hc c (complete _ _ _ h) have hb := (reflect _ _ _).mpr h simp [hb] at this exact this · rintro ⟨hs, hc⟩ refine ⟨hs, fun c hm => ?_⟩ by_cases h : isCombinationBool input.1 input.2 c = true · exact Or.inr (hc c ((reflect _ _ _).mp h)) · exact Or.inl (Bool.eq_false_iff.mpr h) theorem increasing_reflect (l : List Nat) : isStrictlyIncreasing l = true ↔ l.Pairwise (· < ·) := by induction l with | nil => simp [isStrictlyIncreasing] | cons x xs ih => cases xs with | nil => simp [isStrictlyIncreasing] | cons y ys => simp only [isStrictlyIncreasing, Bool.and_eq_true, Nat.ble_eq, List.pairwise_cons_cons_iff_of_trans, ← ih] exact and_congr (by omega) Iff.rfl theorem combination_reflect : ∀ n k l, isCombinationBool n k l = true ↔ IsCombination n k l := by intro n k l simp only [isCombinationBool, Bool.and_eq_true, Nat.ble_eq, increasing_reflect, List.all_eq_true, IsCombination] constructor · rintro ⟨⟨⟨h₁, h₂⟩, hp⟩, hr⟩ exact ⟨Nat.le_antisymm h₁ h₂, hp, hr⟩ · rintro ⟨hl, hp, hr⟩ exact ⟨⟨⟨hl.le, hl.ge⟩, hp⟩, hr⟩ theorem combinations_ready (complete : ∀ n k l, IsCombination n k l → l ∈ combinationCandidates n k) (input : Input) (result : Output) : combinations_check input result ↔ combinations_spec input result := by exact combinations_root combination_reflect complete input result /-- On valid input the checker accepts exactly the specified outputs. -/ theorem combinations_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : combinations_check input result ↔ combinations_spec input result := by exact combinations_ready combination_complete input result /-! ### Main algorithm (impl) -/ /-- Combinations of `k` numbers from `lo..hi`, enumerated in lexicographic order by structural recursion on `k`: pick the smallest element `i` from the range, then extend each `(k-1)`-combination of `i+1..hi` with `i` in front. -/ def combineFrom : Nat → Nat → Nat → List (List Nat) | _, _, 0 => [[]] | lo, hi, k + 1 => (List.range' lo (hi - k - lo + 1)).flatMap fun i => (combineFrom (i + 1) hi k).map fun c => i :: c /-- All `k`-combinations of `1..n`, in the lexicographic order the frozen tests expect. -/ def combine (input : Input) : Output := combineFrom 1 input.1 input.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem combine_correct (input : Input) (h : isValidInput input) : combinations_spec input (combine input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (4, 2) #guard isValidInput (1, 1) #guard isValidInput (9, 9) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (0, 1)) #guard !(isValidInput (2, 3)) #guard !(isValidInput (21, 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard combinations_check (4, 2) [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] #guard combinations_check (1, 1) [[1]] #guard combinations_check (9, 9) [[1, 2, 3, 4, 5, 6, 7, 8, 9]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(combinations_check (4, 2) [[1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]) #guard !(combinations_check (1, 1) []) #guard !(combinations_check (9, 9) [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 3, 4, 5, 6, 7, 8]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard combine (4, 2) == [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] #guard combine (1, 1) == [[1]] #guard combine (9, 9) == [[1, 2, 3, 4, 5, 6, 7, 8, 9]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard combinations_check (4, 2) (combine (4, 2)) #guard combinations_check (1, 1) (combine (1, 1)) #guard combinations_check (9, 9) (combine (9, 9)) end PCombinations