import Mathlib /-! # Permutations Ii Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order. ## Constraints - 1 <= nums.length <= 8 - -10 <= nums[i] <= 10 ## Provided examples - `nums = [1, 1, 2]` → `[[1, 1, 2], [1, 2, 1], [2, 1, 1]]` - `nums = [1, 2, 3]` → `[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]` - `nums = [1]` → `[[1]]` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 8. empty where at least one element is required) - invalid input: `nums = [11]` ([structural] a predicate that admits -10 <= nums[i] <= 10. one past the maximum element value) - invalid input: `nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]` ([structural] a predicate that admits 1 <= nums.length <= 8. one past the maximum length) - `nums = [1, 1, 2]` → `[[1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 1, 2]]` is wrong ([structural] uniqueness constraint omitted. all true permutations appear but one is duplicated) - `nums = [1, 2, 3]` → `[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [1, 2, 3]]` is wrong ([structural] uniqueness condition dropped; duplicate permutations allowed. contains all six plus a duplicate, so only uniqueness fails) - `nums = [1]` → `[[1], [1, 1]]` is wrong ([structural] does not enforce that each output list has length equal to nums. includes a list of length 2) -/ namespace PPermutationsIi abbrev Input := List Int abbrev Output := List (List Int) /-! ### Validity predicate (V) -/ /-- Valid input: a list of 1 to 8 integers, each between -10 and 10 inclusive. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 8 && input.all (fun x => -10 ≤ x && x ≤ 10) /-! ### Ideal specification (P_spec) -/ /-- `result` lists every unique permutation of `nums`: it has no duplicate entries, every entry is a permutation of `nums`, and every permutation of `nums` appears as an entry. -/ def uniquePermutations_spec (input : Input) (result : Output) : Prop := result.Nodup ∧ (∀ p ∈ result, p.Perm input) ∧ (∀ p : List Int, p.Perm input → p ∈ result) /-! ### Decidable specification (P_check) -/ /-- Executable checker for `uniquePermutations_spec`: the two permutation clauses are evaluated over the finite candidate list `input.permutations`, which by `List.mem_permutations` contains exactly the permutations of `input`. -/ def uniquePermutations_check (input : Input) (result : Output) : Bool := decide (result.Nodup ∧ (∀ p ∈ result, p ∈ input.permutations) ∧ (∀ p ∈ input.permutations, p ∈ result)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem uniquePermutations_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : uniquePermutations_check input result ↔ uniquePermutations_spec input result := by simp [uniquePermutations_check, uniquePermutations_spec, List.mem_permutations] /-! ### Implementation helpers -/ /-- Insert `x` into a sorted duplicate-free list, keeping it sorted and duplicate-free. -/ def insertUnique (x : Int) : List Int → List Int | [] => [x] | y :: ys => if x < y then x :: y :: ys else if x = y then y :: ys else y :: insertUnique x ys /-- Sorted list of the distinct values of `xs`, each paired with its multiplicity in `xs`. -/ def countFrequency (xs : List Int) : List (Int × Nat) := (xs.foldl (fun acc x => insertUnique x acc) []).map (fun x => (x, xs.count x)) /-- Sum of the multiplicities in a frequency list. -/ def totalCount (counts : List (Int × Nat)) : Nat := (counts.map Prod.snd).sum /-- All completions of the reversed prefix `pref` from the frequencies in `passed ++ pending`, trying each entry of `pending` as the next value. -/ def generateFromCounts (passed pending : List (Int × Nat)) (pref : List Int) : List (List Int) := match pending with | [] => if passed.all (fun p => p.2 = 0) then [pref.reverse] else [] | (x, c) :: rest => (if h : c = 0 then [] else generateFromCounts [] (passed ++ (x, c - 1) :: rest) (x :: pref)) ++ generateFromCounts (passed ++ [(x, c)]) rest pref termination_by (totalCount passed + totalCount pending, pending.length) decreasing_by · simp_wf apply Prod.Lex.left simp only [totalCount, List.map_nil, List.map_cons, List.map_append, List.sum_nil, List.sum_cons, List.sum_append] omega · simp_wf rw [show totalCount (passed ++ [(x, c)]) + totalCount rest = totalCount passed + totalCount ((x, c) :: rest) by simp only [totalCount, List.map_nil, List.map_cons, List.map_append, List.sum_nil, List.sum_cons, List.sum_append] omega] apply Prod.Lex.right simp /-! ### Main algorithm (impl) -/ /-- Unique permutations in lexicographic order by backtracking over the sorted frequency table of `input`. -/ def permuteUnique (input : Input) : Output := generateFromCounts [] (countFrequency input) [] /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem permuteUnique_correct (input : Input) (h : isValidInput input) : uniquePermutations_spec input (permuteUnique input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 1, 2] #guard isValidInput [1, 2, 3] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [11]) #guard !(isValidInput [1, 2, 3, 4, 5, 6, 7, 8, 9]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard uniquePermutations_check [1, 1, 2] [[1, 1, 2], [1, 2, 1], [2, 1, 1]] #guard uniquePermutations_check [1, 2, 3] [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] #guard uniquePermutations_check [1] [[1]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(uniquePermutations_check [1, 1, 2] [[1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 1, 2]]) #guard !(uniquePermutations_check [1, 2, 3] [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [1, 2, 3]]) #guard !(uniquePermutations_check [1] [[1], [1, 1]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard permuteUnique [1, 1, 2] == [[1, 1, 2], [1, 2, 1], [2, 1, 1]] #guard permuteUnique [1, 2, 3] == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] #guard permuteUnique [1] == [[1]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard uniquePermutations_check [1, 1, 2] (permuteUnique [1, 1, 2]) #guard uniquePermutations_check [1, 2, 3] (permuteUnique [1, 2, 3]) #guard uniquePermutations_check [1] (permuteUnique [1]) end PPermutationsIi