heapBlockBase
The 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 identity, and the (q + 1)-th obtained from the q-th by composing with the tail-extended final permutation of order n and the block transition swap.
Statement
def heapBlockBase (n : ℕ) : ℕ → Equiv.Perm (Fin (n + 1))- Defined in
- arXiv:2611.05397 Definition 7
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Built on 3
- heapBlockSwapThe top-level transposition swap between block j and block j + 1 in the order-(n + 1) Heap algorithm, which for j < n swaps the trailing…
- permExtendLastThe canonical extension of a permutation of Fin n to a permutation of Fin (n + 1) that fixes the trailing element Fin.last n.
- heap_final_permThe permutation of Fin m induced by the final arrangement array of the order-m Heap algorithm.
- Used by 2
- heapPermSeqThe r-th permutation in the Heap output sequence of order n, defined for order k + 2 by decomposing r into block index q = r / (k + 1)!…
- heapUnrankThe Heap permutation unranking map heapUnrank assigns to each dimension n : ℕ and factorial-base code d : HeapCode n a permutation of Fin…
Read back from the Lean
heapBlockBase is a function that takes a natural number n : ℕ and recursively defines a sequence of permutations of Fin (n + 1) indexed by q : ℕ:
- Base case: heapBlockBase n 0 is the identity permutation on Fin (n + 1).
- Inductive step: heapBlockBase n (q + 1) is the group product heapBlockBase n q * permExtendLast (heap_final_perm n) * heapBlockSwap n q in Equiv.Perm (Fin (n + 1)).
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 block base permutation C_{n+1, q} of the order-(n + 1) Heap algorithm. -/ def heapBlockBase (n : ℕ) : ℕ → Equiv.Perm (Fin (n + 1)) | 0 => 1 | q + 1 => heapBlockBase n q * permExtendLast (heap_final_perm n) * heapBlockSwap n q