import Mathlib /-! # Permutation Sequence The set [1, 2, 3, ..., n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence. ## Constraints - 1 <= n <= 9 - 1 <= k <= n! ## Provided examples - `n = 3, k = 3` → `"213"` - `n = 4, k = 9` → `"2314"` - `n = 3, k = 1` → `"123"` ## Synthesized negative examples - invalid input: `n = 0, k = 1` ([structural] a predicate that admits 1 <= n <= 9. n one below the stated floor) - invalid input: `n = 3, k = 7` ([structural] a predicate that admits 1 <= k <= n!. k exceeds n! for this n; absolute range check accepts) - invalid input: `n = 10, k = 1` ([structural] a predicate that admits 1 <= n <= 9. n one above the stated ceiling) - `n = 3, k = 3` → `"231"` is wrong ([structural] k counted from 0 rather than 1. zero-indexed third permutation) - `n = 4, k = 9` → `"2143"` is wrong ([structural] k is decremented once too often, returning the (k-1)th permutation instead of the kth. returns the 8th permutation for k=9) - `n = 3, k = 1` → `"132"` is wrong ([structural] the kth index is interpreted as zero-based instead of 1-based. for k=1, zero-based gives the second permutation) -/ namespace PPermutationSequence abbrev Input := (Nat) × (Nat) abbrev Output := String /-! ### Specification helpers -/ /-- `p` is a permutation of the list `[1, 2, ..., n]`. -/ def isPermOfRange (n : Nat) (p : List Nat) : Prop := p.Perm (List.range' 1 n) /-- The string obtained by writing the elements of `p` in decimal, one after another. -/ def digitConcat (p : List Nat) : String := String.join (p.map toString) /-- Exactly `m` permutations of `[1, 2, ..., n]` precede `p` in lexicographic order. -/ def lexPredecessorCount (n : Nat) (p : List Nat) (m : Nat) : Prop := Set.ncard {q : List Nat | isPermOfRange n q ∧ q < p} = m /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ n ≤ 9` and `1 ≤ k ≤ n!`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1 && input.1 ≤ 9 && 1 ≤ input.2 && input.2 ≤ input.1.factorial /-! ### Ideal specification (P_spec) -/ /-- `result` is the concatenation in decimal of some permutation `p` of `[1, 2, ..., n]`, where exactly `k - 1` permutations of `[1, 2, ..., n]` precede `p` lexicographically. -/ def kthPermutation_spec (input : Input) (result : Output) : Prop := ∃ p : List Nat, isPermOfRange input.1 p ∧ result = digitConcat p ∧ lexPredecessorCount input.1 p (input.2 - 1) /-! ### Decidable specification (P_check) -/ /-- Executable checker for `kthPermutation_spec`: `p` ranges over the permutations of `[1, ..., n]`, and its lexicographic predecessor count is the length of that list filtered by `· < p`. -/ def kthPermutation_check (input : Input) (result : Output) : Bool := decide (∃ p ∈ (List.range' 1 input.1).permutations, result = digitConcat p ∧ ((List.range' 1 input.1).permutations.filter fun q => decide (q < p)).length = input.2 - 1) theorem permutation_root (count_bridge : ∀ (n : Nat) (p : List Nat), Set.ncard {q : List Nat | isPermOfRange n q ∧ q < p} = ((List.range' 1 n).permutations.filter fun q => decide (q < p)).length) (input : Input) (result : Output) : kthPermutation_check input result ↔ kthPermutation_spec input result := by simp only [kthPermutation_check, decide_eq_true_eq, kthPermutation_spec, lexPredecessorCount] simp_rw [count_bridge] simp only [isPermOfRange, List.mem_permutations] theorem predecessor_card (n : Nat) (p : List Nat) : Set.ncard {q : List Nat | isPermOfRange n q ∧ q < p} = ((List.range' 1 n).permutations.filter fun q => decide (q < p)).length := by let L := (List.range' 1 n).permutations.filter fun q => decide (q < p) have hs : {q : List Nat | isPermOfRange n q ∧ q < p} = (L.toFinset : Set (List Nat)) := by ext q simp only [L, Set.mem_setOf_eq, Finset.mem_coe, List.mem_toFinset, List.mem_filter, List.mem_permutations, decide_eq_true_eq, isPermOfRange] rw [hs, Set.ncard_coe_finset] exact List.toFinset_card_of_nodup ((List.nodup_permutations _ List.nodup_range').filter _) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem kthPermutation_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : kthPermutation_check input result ↔ kthPermutation_spec input result := by exact permutation_root predecessor_card input result /-! ### Implementation helpers -/ /-- The zero-based `idx`-th digit of `ds` together with `ds` with that digit removed. -/ def selectAt (idx : Nat) (ds : List Nat) : Nat × List Nat := (ds.getD idx 0, ds.eraseIdx idx) /-- The permutation of `digits` of zero-based lexicographic rank `m`, built one digit per position by the factorial number system. -/ def buildPermutation : Nat → List Nat → Nat → List Nat | 0, _, _ => [] | _, [], _ => [] | pos + 1, digits, m => let f := pos.factorial let idx := Nat.min (m / f) (digits.length - 1) let (chosen, rest) := selectAt idx digits chosen :: buildPermutation pos rest (m % f) /-! ### Main algorithm (impl) -/ /-- The `k`-th permutation of `[1, ..., n]` in lexicographic order, by the factorial number system: each position's digit is selected from the remaining digits by dividing the zero-based rank `k - 1` by the factorial of the remaining positions. -/ def getKthPermutation (input : Input) : Output := digitConcat (buildPermutation input.1 (List.range' 1 input.1) (input.2 - 1)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem getKthPermutation_correct (input : Input) (h : isValidInput input) : kthPermutation_spec input (getKthPermutation input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (3, 3) #guard isValidInput (4, 9) #guard isValidInput (3, 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (0, 1)) #guard !(isValidInput (3, 7)) #guard !(isValidInput (10, 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard kthPermutation_check (3, 3) "213" #guard kthPermutation_check (4, 9) "2314" #guard kthPermutation_check (3, 1) "123" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(kthPermutation_check (3, 3) "231") #guard !(kthPermutation_check (4, 9) "2143") #guard !(kthPermutation_check (3, 1) "132") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard getKthPermutation (3, 3) == "213" #guard getKthPermutation (4, 9) == "2314" #guard getKthPermutation (3, 1) == "123" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard kthPermutation_check (3, 3) (getKthPermutation (3, 3)) #guard kthPermutation_check (4, 9) (getKthPermutation (4, 9)) #guard kthPermutation_check (3, 1) (getKthPermutation (3, 1)) end PPermutationSequence