AFTD Auto-Formalizing Theoretical Domains

heapPermSeq

def

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)
See it in the graphDiscuss this resultChallenge it