← 研踪 PaperTrailarXiv:2611.05397 · v2
Ranking and Unranking Permutations in Heap's Order
首次提交 2026-10-15 17:00
版本更新 2026-11-09 11:06
雷达观测 2026-11-10 13:18
摘要
Heap's algorithm is a permutation generation method with very low constant overhead. Its element-interchanging mechanism, however, prevents the standard factorial-base Lehmer code from being applied directly, and to our knowledge no explicit Rank/Unrank algorithm for the Heap order has been published. This paper describes the block structure of Heap's algorithm in terms of rearrangement operators: the net effect of a block-internal traversal is a tail-preserving operator and the block-boundary swap is a top-level swap operator, and together they yield a closed-form recurrence for the block transitions. On this basis a bottom-up Unrank algorithm and a top-down Rank algorithm are built from one and the same closed-form in-block mapping; both run in $O(n^3)$ time and $O(n)$ space and require no factorial-scale precomputed table. The supporting proofs use a synchronized strong induction on the dimension to establish the bijectivity of the trailing-element mapping, closed forms for the final arrangement and for the trailing sequence, the dichotomy of its cycle structure, and the reciprocity of Rank and Unrank. The Heap order is in fact the colex order of the mixed-radix code.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-11 14:24 · 最新观测版本
Ranking and Unranking Permutations in Heap's Order
Heap's algorithm is a permutation generation method with very low constant overhead. Its element-interchanging mechanism, however, prevents the standard factorial-base Lehmer code from being applied directly, and to our knowledge no explicit Rank/Unrank algorithm for the Heap order has been published. This paper describes the block structure of Heap's algorithm in terms of rearrangement operators: the net effect of a block-internal traversal is a tail-preserving operator and the block-boundary swap is a top-level swap operator, and together they yield a closed-form recurrence for the block transitions. On this basis a bottom-up Unrank algorithm and a top-down Rank algorithm are built from one and the same closed-form in-block mapping; both run in $O(n^2)$ time and $O(n)$ space and require no factorial-scale precomputed table. The supporting proofs use a synchronized strong induction on the dimension to establish the bijectivity of the trailing-element mapping, closed forms for the final arrangement and for the trailing sequence, the dichotomy of its cycle structure, and the reciprocity of Rank and Unrank. The Heap order is in fact the colex order of the mixed-radix code.
查看此版本解读 →查看此版本原文 ↗v2 · 2026-11-09 11:06
Ranking and Unranking Permutations in Heap's Order
Heap's algorithm is a permutation generation method with very low constant overhead. Its element-interchanging mechanism, however, prevents the standard factorial-base Lehmer code from being applied directly, and to our knowledge no explicit Rank/Unrank algorithm for the Heap order has been published. This paper describes the block structure of Heap's algorithm in terms of rearrangement operators: the net effect of a block-internal traversal is a tail-preserving operator and the block-boundary swap is a top-level swap operator, and together they yield a closed-form recurrence for the block transitions. On this basis a bottom-up Unrank algorithm and a top-down Rank algorithm are built from one and the same closed-form in-block mapping; both run in $O(n^3)$ time and $O(n)$ space and require no factorial-scale precomputed table. The supporting proofs use a synchronized strong induction on the dimension to establish the bijectivity of the trailing-element mapping, closed forms for the final arrangement and for the trailing sequence, the dichotomy of its cycle structure, and the reciprocity of Rank and Unrank. The Heap order is in fact the colex order of the mixed-radix code.
查看此版本解读 →查看此版本原文 ↗