heap_final_perm
The permutation of Fin m induced by the final arrangement array of the order-m Heap algorithm.
Statement
def heap_final_perm (m : ℕ) : Equiv.Perm (Fin m)- Defined in
- arXiv:2611.05397 Definition 3 and Theorem 5
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 1
- heapBlockBaseThe block base permutation for the q-th block of the order-(n + 1) Heap algorithm, defined recursively with the 0-th block base as the…
Read back from the Lean
heap_final_perm defines a function mapping each natural number m : ℕ to a permutation of Fin m (Equiv.Perm (Fin m)), given by cases:
1. If m % 2 = 1 ∧ 3 ≤ m (i.e., m is odd and m ≥ 3), it is the swap (transposition) of 0 and m - 1.
2. Otherwise, if 4 ≤ m (i.e., m is even and m ≥ 4), it is the cyclic permutation List.formPerm on the list whose first element is 0, followed by mid (the elements m - 3, m - 4, ..., 1 obtained by reversing List.range (m - 3) and adding 1 to each element), followed by m - 2 and m - 1.
3. Otherwise, if m = 2, it is the swap (transposition) of 0 and 1.
4. Otherwise (i.e., m = 0 or m = 1), it is the identity permutation 1 on Fin m.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The permutation of `Fin m` induced by the final arrangement array of the order-`m` Heap algorithm. -/ def heap_final_perm (m : ℕ) : Equiv.Perm (Fin m) := if hm : m % 2 = 1 ∧ 3 ≤ m then Equiv.swap ⟨0, by omega⟩ ⟨m - 1, by omega⟩ else if h4 : 4 ≤ m then let zero : Fin m := ⟨0, by omega⟩ let mid : List (Fin m) := ((List.range (m - 3)).reverse.filterMap (fun i => if hi : i + 1 < m then some ⟨i + 1, hi⟩ else none)) let penultimate : Fin m := ⟨m - 2, by omega⟩ let last : Fin m := ⟨m - 1, by omega⟩ List.formPerm (zero :: (mid ++ [penultimate, last])) else if hm2 : m = 2 then Equiv.swap ⟨0, by omega⟩ ⟨1, by omega⟩ else 1