import Mathlib /-! # Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. ## Constraints - 1 <= n <= 8 ## Provided examples - `n = 3` → `["((()))", "(()())", "(())()", "()(())", "()()()"]` - `n = 1` → `["()"]` - `n = 4` → `["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 8. one below the minimum; catches a predicate that forgot the floor) - invalid input: `n = 9` ([structural] a predicate that admits 1 <= n <= 8. one above the maximum; catches a predicate that forgot the ceiling) - invalid input: `n = 100` ([structural] a predicate that admits 1 <= n <= 8. a different order of magnitude above the bound) - `n = 3` → `["((()))", "((()))", "(()())", "(())()", "()(())", "()()()"]` is wrong ([structural] nothing requires each combination to appear exactly once. all true strings are present, but one is duplicated) - `n = 1` → `[]` is wrong ([structural] nothing requires every valid combination to appear. Empty list satisfies a soundness-only reading) - `n = 4` → `["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()", "()()()"]` is wrong ([structural] does not require every string to have exactly n pairs. added a 3-pair string '()()()' to the full list) -/ namespace PGenerateParentheses abbrev Input := Nat abbrev Output := List String /-! ### Specification helpers -/ /-- The parenthesis denoted by a Dyck step. -/ def dyckStepToChar (step : DyckStep) : Char := match step with | DyckStep.U => '(' | DyckStep.D => ')' /-- A string is a well-formed parenthesis string with exactly `n` pairs. -/ def WellFormed (s : String) (n : Nat) : Prop := ∃ w : DyckWord, w.toList.map dyckStepToChar = s.toList ∧ List.count DyckStep.U w.toList = n /-! ### Validity predicate (V) -/ /-- Valid input: a pair count between 1 and 8 inclusive. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 8 /-! ### Ideal specification (P_spec) -/ /-- `result` contains exactly the well-formed parenthesis strings with `input` pairs, each once. -/ def wellFormedParentheses_spec (input : Input) (result : Output) : Prop := (∀ s ∈ result, WellFormed s input) ∧ ∀ s : String, WellFormed s input → List.count s result = 1 /-! ### Decidable specification (P_check) -/ /-- The signed balance step of one character: '(' is +1, ')' is -1, anything else 0. -/ def parenDelta (c : Char) : Int := if c == '(' then 1 else if c == ')' then -1 else 0 /-- Decidable reading of `WellFormed`: only parentheses, `2*n` long, balance never negative and ending at zero. -/ def isWellFormedString (s : String) (n : Nat) : Bool := let cs := s.toList let balances := cs.scanl (fun b c => b + parenDelta c) 0 cs.all (fun c => c == '(' || c == ')') && cs.length == 2 * n && balances.all (fun b => decide (0 ≤ b)) && balances.getLast? == some 0 /-- All sublists of `l` of length exactly `k`, each in the order of `l`. -/ def chooseSublists : Nat → List Nat → List (List Nat) | 0, _ => [[]] | _ + 1, [] => [] | k + 1, x :: xs => (chooseSublists k xs).map (x :: ·) ++ chooseSublists (k + 1) xs /-- The length-`m` parenthesis string whose '(' positions are exactly `opens`. -/ def parensFromOpens (m : Nat) (opens : List Nat) : String := String.ofList ((List.range m).map (fun i => if opens.contains i then '(' else ')')) /-- Every well-formed parenthesis string with `n` pairs, decoded from the `n`-subsets of the `2*n` positions. -/ def wellFormedStringsOf (n : Nat) : List String := ((chooseSublists n (List.range (2 * n))).map (parensFromOpens (2 * n))).filter (fun s => isWellFormedString s n) /-- Executable checker for `wellFormedParentheses_spec` over the finite candidate strings. -/ def wellFormedParentheses_check (input : Input) (result : Output) : Bool := result.all (fun s => isWellFormedString s input) && (wellFormedStringsOf input).all (fun s => List.count s result == 1) theorem root_of_bridges (reflection : ∀ s n, isWellFormedString s n = true ↔ WellFormed s n) (coverage : ∀ s n, WellFormed s n → s ∈ (chooseSublists n (List.range (2*n))).map (parensFromOpens (2*n))) (input : Input) (result : Output) : wellFormedParentheses_check input result ↔ wellFormedParentheses_spec input result := by simp only [wellFormedParentheses_check, Bool.and_eq_true, List.all_eq_true, beq_iff_eq, wellFormedParentheses_spec] constructor · rintro ⟨hs, hc⟩ exact ⟨fun s h => (reflection s input).mp (hs s h), fun s h => hc s (List.mem_filter.mpr ⟨coverage s input h, (reflection s input).mpr h⟩)⟩ · rintro ⟨hs, hc⟩ exact ⟨fun s h => (reflection s input).mpr (hs s h), fun s h => hc s ((reflection s input).mp (List.mem_filter.mp h).2)⟩ lemma fold_steps (xs : List DyckStep) (b : Int) : (xs.map dyckStepToChar).foldl (fun b c => b + parenDelta c) b = b + (xs.count DyckStep.U : Int) - (xs.count DyckStep.D : Int) := by induction xs generalizing b with | nil => simp | cons x xs ih => simp only [List.map_cons, List.foldl_cons, ih] cases x <;> simp [dyckStepToChar, parenDelta] <;> omega lemma steps_length (xs : List DyckStep) : xs.length = xs.count DyckStep.U + xs.count DyckStep.D := by induction xs with | nil => simp | cons x xs ih => cases x <;> simp_all <;> omega lemma scan_nonneg (cs : List Char) : (cs.scanl (fun b c => b + parenDelta c) (0 : Int)).all (fun b => decide (0 ≤ b)) = true ↔ ∀ i, 0 ≤ (cs.take i).foldl (fun b c => b + parenDelta c) (0 : Int) := by simp only [List.all_eq_true, decide_eq_true_eq] constructor · intro h have hb (i : Nat) (hi : i ≤ cs.length) : 0 ≤ (cs.take i).foldl (fun b c => b + parenDelta c) (0 : Int) := by have hh : i < (cs.scanl (fun b c => b + parenDelta c) (0 : Int)).length := by simp; omega simpa only [List.getElem_scanl] using h _ (List.getElem_mem hh) intro i by_cases hi : i ≤ cs.length · exact hb i hi · simpa only [List.take_of_length_le (by omega : cs.length ≤ i), List.take_length] using hb cs.length (le_refl _) · intro h b hb obtain ⟨i, hi, rfl⟩ := List.mem_iff_getElem.mp hb simpa only [List.getElem_scanl] using h i lemma test_map (xs : List DyckStep) (n : Nat) : isWellFormedString (String.ofList (xs.map dyckStepToChar)) n = true ↔ xs.count DyckStep.U = xs.count DyckStep.D ∧ (∀ i, (xs.take i).count DyckStep.D ≤ (xs.take i).count DyckStep.U) ∧ xs.count DyckStep.U = n := by have ha : (xs.map dyckStepToChar).all (fun c => c == '(' || c == ')') = true := by simp only [List.all_eq_true, List.mem_map] rintro c ⟨x, hx, rfl⟩ cases x <;> decide simp only [isWellFormedString, String.toList_ofList, Bool.and_eq_true, ha, true_and, beq_iff_eq, List.length_map, scan_nonneg, List.getLast?_scanl, Option.some.injEq, ← List.map_take, fold_steps, zero_add] have hl := steps_length xs constructor · rintro ⟨⟨hlen, hp⟩, he⟩ refine ⟨by omega, fun i => ?_, by omega⟩ have := hp i omega · rintro ⟨he, hp, hn⟩ exact ⟨⟨by omega, fun i => by have := hp i; omega⟩, by omega⟩ lemma encode_chars (cs : List Char) (h : ∀ c ∈ cs, c = '(' ∨ c = ')') : (cs.map (fun c => if c = '(' then DyckStep.U else DyckStep.D)).map dyckStepToChar = cs := by induction cs with | nil => rfl | cons c cs ih => have hc := h c (by simp) have ht := ih (fun c hc => h c (by simp [hc])) rcases hc with rfl | rfl <;> simp [dyckStepToChar, ht] theorem reflection (s : String) (n : Nat) : isWellFormedString s n = true ↔ WellFormed s n := by constructor · intro h have ha : ∀ c ∈ s.toList, c = '(' ∨ c = ')' := by have hh := h simp only [isWellFormedString, Bool.and_eq_true] at hh simpa only [List.all_eq_true, Bool.or_eq_true, beq_iff_eq] using hh.1.1.1 let xs := s.toList.map (fun c => if c = '(' then DyckStep.U else DyckStep.D) have he : xs.map dyckStepToChar = s.toList := encode_chars _ ha have hs : String.ofList (xs.map dyckStepToChar) = s := by rw [he]; simp have hp := (test_map xs n).mp (by rwa [hs]) exact ⟨⟨xs, hp.1, hp.2.1⟩, he, hp.2.2⟩ · rintro ⟨w, he, hn⟩ have hs : String.ofList (w.toList.map dyckStepToChar) = s := by rw [he]; simp rw [← hs] exact (test_map w.toList n).mpr ⟨w.count_U_eq_count_D, w.count_D_le_count_U, hn⟩ lemma findIdxs_sublist_range' (xs : List α) (p : α → Bool) (s : Nat) : List.Sublist (xs.findIdxs p s) (List.range' s xs.length) := by induction xs generalizing s with | nil => simp | cons x xs ih => simp only [List.findIdxs_cons, List.length_cons, List.range'_succ] split · exact (ih (s + 1)).cons_cons s · exact (ih (s + 1)).cons s lemma findIdxs_sublist_range (xs : List α) (p : α → Bool) : List.Sublist (xs.findIdxs p) (List.range xs.length) := by simpa only [List.range_eq_range'] using findIdxs_sublist_range' xs p 0 lemma mem_chooseSublists_iff {ys xs : List Nat} {k : Nat} : ys ∈ chooseSublists k xs ↔ List.Sublist ys xs ∧ ys.length = k := by induction xs generalizing k ys with | nil => cases k with | zero => simp [chooseSublists] | succ k => constructor · simp [chooseSublists] · rintro ⟨hsub, hlen⟩ cases hsub simp at hlen | cons x xs ih => cases k with | zero => constructor · intro hm simp [chooseSublists] at hm subst ys simp · rintro ⟨_, hlen⟩ have : ys = [] := List.eq_nil_of_length_eq_zero hlen subst ys simp [chooseSublists] | succ k => constructor · intro hm simp only [chooseSublists, List.mem_append, List.mem_map] at hm rcases hm with ⟨zs, hzs, rfl⟩ | hm · have hz := (ih (ys := zs) (k := k)).mp hzs exact ⟨hz.1.cons_cons x, by simp [hz.2]⟩ · have hy := (ih (ys := ys) (k := k + 1)).mp hm exact ⟨hy.1.cons x, hy.2⟩ · rintro ⟨hsub, hlen⟩ simp only [chooseSublists, List.mem_append, List.mem_map] cases hsub with | cons _ hs => exact Or.inr ((ih (k := k + 1)).mpr ⟨hs, hlen⟩) | cons_cons _ hs => apply Or.inl refine ⟨_, (ih (k := k)).mpr ⟨hs, ?_⟩, rfl⟩ simpa using hlen lemma parensFromOpens_findIdxs (xs : List DyckStep) : parensFromOpens xs.length (xs.findIdxs (· == DyckStep.U)) = String.ofList (xs.map dyckStepToChar) := by apply String.toList_injective simp only [parensFromOpens, String.toList_ofList] apply List.ext_getElem · simp · intro i h₁ h₂ simp only [List.length_map, List.length_range] at h₁ h₂ simp only [List.getElem_map, List.getElem_range] have hb : (xs.findIdxs (· == DyckStep.U)).contains i = (xs[i] == DyckStep.U) := by apply Bool.eq_iff_iff.mpr rw [List.contains_iff_mem, List.mem_findIdxs_iff_pos_getElem h₁] rw [hb] cases xs[i] <;> rfl lemma coverage : ∀ s n, WellFormed s n → s ∈ (chooseSublists n (List.range (2 * n))).map (parensFromOpens (2 * n)) := by intro s n hs rcases hs with ⟨w, hchars, hcount⟩ let opens := w.toList.findIdxs (· == DyckStep.U) have hlen : w.toList.length = 2 * n := by have hc := w.count_U_eq_count_D have hl := steps_length w.toList omega have hopenLen : opens.length = n := by simpa only [opens, List.length_findIdxs, ← List.count_eq_countP] using hcount have hopenSub : List.Sublist opens (List.range (2 * n)) := by rw [← hlen] exact findIdxs_sublist_range w.toList (· == DyckStep.U) have hopenMem : opens ∈ chooseSublists n (List.range (2 * n)) := mem_chooseSublists_iff.mpr ⟨hopenSub, hopenLen⟩ apply List.mem_map.mpr refine ⟨opens, hopenMem, ?_⟩ calc parensFromOpens (2 * n) opens = parensFromOpens w.toList.length opens := by rw [hlen] _ = String.ofList (w.toList.map dyckStepToChar) := parensFromOpens_findIdxs w.toList _ = s := by rw [hchars, String.ofList_toList] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem wellFormedParentheses_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : wellFormedParentheses_check input result ↔ wellFormedParentheses_spec input result := by exact root_of_bridges reflection coverage input result /-! ### Implementation helpers -/ /-- The backtracking loop: all completions of the reversed prefix `acc` with `n` pairs once `opens` '(' and `closes` ')' have been used. -/ def generate (n opens closes : Nat) (ho : opens ≤ n) (hc : closes ≤ n) (balance : Int) (acc : List Char) : List String := if opens = n && closes = n then [String.ofList acc.reverse] else let withOpen := if h : opens < n then generate n (opens + 1) closes h hc (balance + parenDelta '(') ('(' :: acc) else [] let withClose := if h : closes < opens then generate n opens (closes + 1) ho (Nat.lt_of_lt_of_le h ho) (balance + parenDelta ')') (')' :: acc) else [] withOpen ++ withClose termination_by 2 * n - (opens + closes) /-! ### Main algorithm (impl) -/ /-- All well-formed parenthesis strings with `input` pairs, by depth-first backtracking over valid prefixes, '(' tried before ')'. -/ def generateParentheses (input : Input) : Output := generate input 0 0 (Nat.zero_le input) (Nat.zero_le input) 0 [] /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem generateParentheses_correct (input : Input) (h : isValidInput input) : wellFormedParentheses_spec input (generateParentheses input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 3 #guard isValidInput 1 #guard isValidInput 4 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 9) #guard !(isValidInput 100) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard wellFormedParentheses_check 3 ["((()))", "(()())", "(())()", "()(())", "()()()"] #guard wellFormedParentheses_check 1 ["()"] #guard wellFormedParentheses_check 4 ["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(wellFormedParentheses_check 3 ["((()))", "((()))", "(()())", "(())()", "()(())", "()()()"]) #guard !(wellFormedParentheses_check 1 []) #guard !(wellFormedParentheses_check 4 ["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()", "()()()"]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard generateParentheses 3 == ["((()))", "(()())", "(())()", "()(())", "()()()"] #guard generateParentheses 1 == ["()"] #guard generateParentheses 4 == ["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard wellFormedParentheses_check 3 (generateParentheses 3) #guard wellFormedParentheses_check 1 (generateParentheses 1) #guard wellFormedParentheses_check 4 (generateParentheses 4) end PGenerateParentheses