heapPermSeq
The 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)! and in-block index rem = r % (k + 1)!, composing the block base array with the tail-extended rem-th permutation of order k + 1.
Statement
def heapPermSeq : (n : ℕ) → ℕ → Equiv.Perm (Fin n)- Defined in
- arXiv:2611.05397 Lemma 2
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Built on 2
- 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.
Read back from the Lean
heapPermSeq is a recursively defined function taking two natural numbers, n : ℕ and r : ℕ, and returning a permutation of Fin n (Equiv.Perm (Fin n)):
1. For n = 0 and any r : ℕ, it returns the identity permutation 1 on Fin 0.
2. For n = 1 and any r : ℕ, it returns the identity permutation 1 on Fin 1.
3. For n = k + 2 (where k : ℕ) and any r : ℕ, let:
- f = (k + 1)! (the factorial of k + 1),
- q = r / f (natural division),
- rem = r % f (remainder modulo f).
Then it returns the permutation composition:
heapBlockBase (k + 1) q * permExtendLast (heapPermSeq (k + 1) rem)
in the group 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 r-th permutation in the Heap output sequence of order n. -/ def heapPermSeq : (n : ℕ) → ℕ → Equiv.Perm (Fin n) | 0, _ => 1 | 1, _ => 1 | k + 2, r => let f := (k + 1).factorial let q := r / f let rem := r % f heapBlockBase (k + 1) q * permExtendLast (heapPermSeq (k + 1) rem)