import Mathlib /-! # Permutations Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. ## Constraints - 1 <= nums.length <= 6 - -10 <= nums[i] <= 10 - All the integers of nums are unique. ## Provided examples - `nums = [1, 2, 3]` → `[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]` - `nums = [0, 1]` → `[[0, 1], [1, 0]]` - `nums = [1]` → `[[1]]` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 6. empty where at least one element is required) - invalid input: `nums = [11]` ([structural] a predicate that admits -10 <= nums[i] <= 10. one past the stated maximum value) - invalid input: `nums = [1, 1]` ([structural] a predicate that admits All the integers of nums are unique.. duplicate values; a predicate checking only length and range accepts it) - `nums = [1, 2, 3]` → `[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [1, 2]]` is wrong ([structural] does not require each inner list to be a permutation of nums. extra list has length 2, not 3) - `nums = [0, 1]` → `[[0, 1]]` is wrong ([structural] all possible permutations not required. Returns one valid permutation, omits the other.) - `nums = [1]` → `[]` is wrong ([structural] completeness stated as soundness alone. empty list vacuously contains only valid permutations) -/ namespace PPermutations abbrev Input := List Int abbrev Output := List (List Int) /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 6 distinct integers, each between -10 and 10 inclusive. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.length) && decide (input.length ≤ 6) && input.all (fun x => decide (-10 ≤ x ∧ x ≤ 10)) && decide input.Nodup /-! ### Ideal specification (P_spec) -/ /-- `result` lists the permutations of `input`: it has exactly `input.length`! entries, every entry is a permutation of `input`, and every permutation of `input` occurs as an entry, in any order. -/ def permutations_spec (input : Input) (result : Output) : Prop := (result.length = input.length.factorial ∧ ∀ q ∈ result, q.Perm input) ∧ ∀ p : List Int, p.Perm input → p ∈ result /-! ### Decidable specification (P_check) -/ /-- Executable checker for `permutations_spec`, quantifying over the finite `input.permutations` instead of all lists. -/ def permutations_check (input : Input) (result : Output) : Bool := decide ((result.length = input.length.factorial ∧ ∀ q ∈ result, q.Perm input) ∧ ∀ p ∈ input.permutations, p ∈ result) /-- Bridge: membership in the finite enumeration `input.permutations` is exactly the specification's unbounded permutation predicate. -/ theorem mem_permutations_iff_perm (input p : List Int) : p ∈ input.permutations ↔ p.Perm input := by exact List.mem_permutations /-- On valid input the checker accepts exactly the specified outputs. -/ theorem permutations_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : permutations_check input result ↔ permutations_spec input result := by unfold permutations_check permutations_spec simp only [decide_eq_true_eq] refine and_congr Iff.rfl (forall_congr' fun p => ?_) constructor · intro h hp exact h ((mem_permutations_iff_perm input p).mpr hp) · intro h hm exact h ((mem_permutations_iff_perm input p).mp hm) /-! ### Main algorithm (impl) -/ /-- Lexicographic less-or-equal comparison on lists of integers. -/ def lexLE : List Int → List Int → Bool | [], _ => true | _ :: _, [] => false | x :: xs, y :: ys => if x == y then lexLE xs ys else decide (x ≤ y) /-- Enumerates all permutations using the library's total permutation enumerator, sorted into lexicographic order. -/ def generatePermutations (nums : Input) : Output := (List.permutations nums).mergeSort lexLE /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem generatePermutations_correct (input : Input) (h : isValidInput input) : permutations_spec input (generatePermutations input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 3] #guard isValidInput [0, 1] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [11]) #guard !(isValidInput [1, 1]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard permutations_check [1, 2, 3] [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] #guard permutations_check [0, 1] [[0, 1], [1, 0]] #guard permutations_check [1] [[1]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(permutations_check [1, 2, 3] [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [1, 2]]) #guard !(permutations_check [0, 1] [[0, 1]]) #guard !(permutations_check [1] []) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard generatePermutations [1, 2, 3] == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] #guard generatePermutations [0, 1] == [[0, 1], [1, 0]] #guard generatePermutations [1] == [[1]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard permutations_check [1, 2, 3] (generatePermutations [1, 2, 3]) #guard permutations_check [0, 1] (generatePermutations [0, 1]) #guard permutations_check [1] (generatePermutations [1]) end PPermutations