import Mathlib /-! # Next Permutation A permutation of an array of integers is an arrangement of its members into a sequence or linear order. For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order). For example, the next permutation of arr = [1,2,3] is [1,3,2]. Similarly, the next permutation of arr = [2,3,1] is [3,1,2]. While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement. Given an array of integers nums, find the next permutation of nums. The replacement must be in place and use only constant extra memory. ## Constraints - 1 <= nums.length <= 100 - 0 <= nums[i] <= 100 ## Provided examples - `nums = [1, 2, 3]` → `[1, 3, 2]` - `nums = [3, 2, 1]` → `[1, 2, 3]` - `nums = [1, 1, 5]` → `[1, 5, 1]` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 100. empty array below required minimum) - invalid input: `nums = [-1]` ([structural] a predicate that admits 0 <= nums[i] <= 100. negative element outside allowed values) - invalid input: `nums = [101]` ([structural] a predicate that admits 0 <= nums[i] <= 100. one past maximum element value) - `nums = [1, 2, 3]` → `[2, 1, 3]` is wrong ([structural] exact position in lexicographic order omitted. true next is 132; this is one later) - `nums = [3, 2, 1]` → `[3, 2, 2]` is wrong ([structural] the output is not required to be a permutation, only a lexicographically greater sequence. Only the last element incremented; no permutation requirement.) - `nums = [1, 1, 5]` → `[1, 1, 6]` is wrong ([structural] no soundness condition forces the answer to be a permutation. lies between input and every valid greater permutation) -/ namespace PNextPermutation abbrev Input := List Int abbrev Output := List Int /-! ### Specification helpers -/ /-- Some permutation of `l` is lexicographically greater than `l`. -/ def hasGreaterPerm (l : List Int) : Prop := ∃ p : List Int, p.Perm l ∧ l < p /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty list of at most 100 integers, each between 0 and 100. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 100 && input.all (fun x => 0 ≤ x && x ≤ 100) /-! ### Ideal specification (P_spec) -/ /-- `result` is the next permutation of `input`: a permutation that is the least lexicographically greater one when one exists, and otherwise no permutation is smaller. -/ def nextPermutation_spec (input : Input) (result : Output) : Prop := result.Perm input ∧ (hasGreaterPerm input → IsLeast {p : List Int | p.Perm input ∧ input < p} result) ∧ (¬ hasGreaterPerm input → ∀ p : List Int, p.Perm input → ¬ p < result) /-! ### Decidable specification (P_check) -/ /-- Executable checker for `nextPermutation_spec`, quantifying over `input.permutations`. -/ def nextPermutation_check (input : Input) (result : Output) : Bool := decide (result.Perm input ∧ ((∃ p ∈ input.permutations, input < p) → (result ∈ input.permutations ∧ input < result) ∧ ∀ p ∈ input.permutations, input < p → result ≤ p) ∧ ((¬ ∃ p ∈ input.permutations, input < p) → ∀ p ∈ input.permutations, ¬ p < result)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem nextPermutation_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : nextPermutation_check input result ↔ nextPermutation_spec input result := by simp [nextPermutation_check, nextPermutation_spec, hasGreaterPerm, List.mem_permutations, IsLeast, lowerBounds] grind only [] /-! ### Implementation helpers -/ /-- Rightmost ascent of `l`: the prefix, the pivot, and the non-increasing suffix after it, or none if `l` is non-increasing. -/ def findRightmostAscent : List Int → Option (List Int × Int × List Int) | [] => none | [_] => none | x :: y :: rest => match findRightmostAscent (y :: rest) with | some (pre, p, suf) => some (x :: pre, p, suf) | none => if x < y then some ([], x, y :: rest) else none /-- Split a suffix at `pivot` into the leading block of elements strictly greater than `pivot` and the remaining tail. -/ def findRightmostGreaterInSuffix (pivot : Int) : List Int → List Int × List Int | [] => ([], []) | x :: xs => if pivot < x then let (gt, tail) := findRightmostGreaterInSuffix pivot xs (x :: gt, tail) else ([], x :: xs) /-- Swap `pivot` with the rightmost greater suffix element and reverse the suffix into ascending order. -/ def swapAndReverseSuffix (pre : List Int) (pivot : Int) (suffix : List Int) : List Int := let (gt, tail) := findRightmostGreaterInSuffix pivot suffix match gt.reverse with | [] => pre ++ (pivot :: suffix.reverse) | swapper :: gtRev => pre ++ (swapper :: (tail.reverse ++ (pivot :: gtRev))) /-! ### Main algorithm (impl) -/ /-- Next permutation by a right-to-left pivot scan, a swap with the rightmost greater suffix element, and a suffix reversal, each linear in the list length. -/ def nextPermutationImpl (input : Input) : Output := match findRightmostAscent input with | none => input.reverse | some (pre, pivot, suffix) => swapAndReverseSuffix pre pivot suffix /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem nextPermutationImpl_correct (input : Input) (h : isValidInput input) : nextPermutation_spec input (nextPermutationImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 2, 3] #guard isValidInput [3, 2, 1] #guard isValidInput [1, 1, 5] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-1)]) #guard !(isValidInput [101]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard nextPermutation_check [1, 2, 3] [1, 3, 2] #guard nextPermutation_check [3, 2, 1] [1, 2, 3] #guard nextPermutation_check [1, 1, 5] [1, 5, 1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(nextPermutation_check [1, 2, 3] [2, 1, 3]) #guard !(nextPermutation_check [3, 2, 1] [3, 2, 2]) #guard !(nextPermutation_check [1, 1, 5] [1, 1, 6]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard nextPermutationImpl [1, 2, 3] == [1, 3, 2] #guard nextPermutationImpl [3, 2, 1] == [1, 2, 3] #guard nextPermutationImpl [1, 1, 5] == [1, 5, 1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard nextPermutation_check [1, 2, 3] (nextPermutationImpl [1, 2, 3]) #guard nextPermutation_check [3, 2, 1] (nextPermutationImpl [3, 2, 1]) #guard nextPermutation_check [1, 1, 5] (nextPermutationImpl [1, 1, 5]) end PNextPermutation