heapUnrank
The Heap permutation unranking map heapUnrank assigns to each dimension n : ℕ and factorial-base code d : HeapCode n a permutation of Fin n. For n = 0 and n = 1, it returns the identity permutation 1. For n = k + 2, it returns the group product heapBlockBase (k + 1) q * permExtendLast (heapUnrank (k + 1) prefixCode) with the block base permutation on the left and the tail-extended recursive unrank on the right, where q = (d ⟨k, by omega⟩).val : ℕ and prefixCode : HeapCode (k + 1) is defined by prefixCode i = d ⟨i.val, by omega⟩.
Statement
def heapUnrank : (n : ℕ) → HeapCode n → Equiv.Perm (Fin n)- Defined in
- arXiv:2611.05397 Definition 8
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Built on 3
- 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…
- permExtendLastThe canonical extension of a permutation of Fin n to a permutation of Fin (n + 1) that fixes the trailing element Fin.last n.
- HeapCodeThe mixed-radix factorial-base code space for permutations of order n, consisting of tuples d where d_i ranges from 0 to i + 1 for each i…
Read back from the Lean
heapUnrank is a recursive definition that takes a natural number n : ℕ and a code d : HeapCode n, and produces a permutation of Fin n (Equiv.Perm (Fin n)):
1. **Base case n = 0:** returns the identity permutation 1 on Fin 0.
2. **Base case n = 1:** returns the identity permutation 1 on Fin 1.
3. **Inductive step n = k + 2:** given d : HeapCode (k + 2):
- defines prefixCode : HeapCode (k + 1) by restricting d to Fin k (i.e., fun i => d ⟨i.val, _⟩),
- defines q : ℕ as the value (d ⟨k, _⟩).val,
- returns the permutation product heapBlockBase (k + 1) q * permExtendLast (heapUnrank (k + 1) prefixCode) in Equiv.Perm (Fin (k + 2)).
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 Heap permutation unranking map from factorial-base codes to permutations. -/ def heapUnrank : (n : ℕ) → HeapCode n → Equiv.Perm (Fin n) | 0, _ => 1 | 1, _ => 1 | k + 2, d => let prefixCode : HeapCode (k + 1) := fun i => d ⟨i.val, by omega⟩ let q : ℕ := (d ⟨k, by omega⟩).val heapBlockBase (k + 1) q * permExtendLast (heapUnrank (k + 1) prefixCode)