A Divide-and-Conquer Engine for Lexicographical Permutations: Accelerating State Evolution via Hybrid Software-Hardware CPU Instructions

Abstract

Traditional lexicographical permutation algorithms, epitomized by \texttt{std::next\_permutation}, are fundamentally bottlenecked by dense control logic and frequent branch mispredictions. This paper introduces LexCHA(Lexicographical Co-designed Hardware Acceleration), a novel hardware-software co-designed architecture that accelerates permutation via native SIMD instructions. Exploiting the inherent fractal isomorphism of permutations, LexCHA decouples global state evolution into a macro software unranking phase and a micro hardware block-construction phase. By utilizing pre-computed deterministic mask streams, LexCHA replaces traditional conditional branching with streaming vector shuffles, achieving a branch-free execution flow. Evaluations demonstrate that LexCHA demonstrates significantly higher throughput than scalar implementations of modern processors, outperforming existing state-of-the-art \texttt{std::next\_permutation} implementations significantly.