Research Paper — Version 4

berkeDet: Data-Parallel Lexicographic Permutation Generation and Streaming Exact Determinant Evaluation via Block Replication and Index Mapping

A new approach to the Leibniz formula: $O(n \cdot n!)$ complexity, lexicographic order, no sorting or per-permutation sign computation — and a compositional structure that is inherently parallel (span $O(n)$, against the chains' $\Omega(n!)$ critical path).

Berke Gülmen  ·  Meryem Gülmen  ·  Ömer Gülmen
Authors Berke Gülmen, Meryem Gülmen, Ömer Gülmen
Version 4 30 July 2026 (first version: 26 February 2026)
Keywords Permutation Generation, Lexicographic Order, Data Parallelism, GPU Computing, Exact Computation, Leibniz Determinant
Complexity $O(n \cdot n!)$ total — span $O(n)$, parallelism $\Theta(n!)$
New — berkeDet for Python. pip install berkeDet brings meryemPer, meryemSign and berkeDet to Windows, macOS and Linux as a compiled package. To our knowledge it is the fastest lexicographic permutation generator for Python: all 39,916,800 permutations of 11 items in 0.077 s — 138× faster than itertools. Examples, benchmarks and a comparison script →

The Problem

The Leibniz formula expresses the determinant of a square matrix as a sum over all $n!$ permutations:

$$\det(A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}$$

To compute this directly, you need two things: all $n!$ permutations of $\{1, 2, \ldots, n\}$ in order, and the sign ($+1$ or $-1$) of each one.

The classical way to do this has three limitations:

  1. Generating the next permutation — the naive lexicographic method requires sorting a suffix at each step ($O(n \log n)$ per permutation). The Narayana Pandita optimization replaces sorting with a suffix reversal, but still scans for a pivot, swaps, and reverses at every step.
  2. Computing the sign — the standard method counts inversions at $O(n^2)$ per permutation; over all $n!$ permutations, $O(n^2 \cdot n!)$.
  3. Serial by construction — every classical generator (naive, Narayana, SJT, Heap) computes permutation $r{+}1$ from the value of permutation $r$. That is a dependency chain with critical path $\Omega(n!)$: no processor count and no implementation language can shorten it, and vector hardware is given nothing to do.

Our Solution

berkeDet removes all three limitations with two subroutines built purely from block replication and index mapping — no sorting, no reversal, no scanning, no inversion counting at any step:

meryemSign generates all $n!$ signs in $\Theta(n!)$ total time — an amortized cost of $O(1)$ per sign. It exploits the recursive block structure of the sign sequence: when extending from $S_{n-1}$ to $S_n$, the signs follow a simple alternating pattern:
$$\underbrace{+\mathbf{s}}_{k=1},\quad \underbrace{-\mathbf{s}}_{k=2},\quad \underbrace{+\mathbf{s}}_{k=3},\quad \underbrace{-\mathbf{s}}_{k=4},\quad \ldots$$
where $\mathbf{s}$ is the sign list for $S_{n-1}$. Isolated measurements: ~100× faster than inversion counting, 350–400× faster than merge-based parity, and 15–18× faster than the strongest classical baseline (Narayana stepping with $O(1)$ incremental parity updates).
meryemPer generates all $n!$ permutations in lexicographic order in $O(n \cdot n!)$ total time. It builds the complete list layer by layer: for each possible first element, it remaps the previous layer's permutations onto the remaining elements. No sorting, no reversal, no pivot scanning appears at any step — the lexicographic order emerges naturally from the construction.
The factorial tree (parallel structure). Every element of a layer is a pure function of one element of the previous layer — siblings never wait for each other. In the work–span model both subroutines have span $O(n)$ and parallelism $\Theta(n!)$. Measured on a single core with vectorized (NumPy) realizations: meryemPer generates all permutations $\approx 6\times$ faster than the C-implemented itertools chain; all 479,001,600 signs of $S_{12}$ in 0.19 seconds; and the exact vectorized $10 \times 10$ determinant runs 15× faster than SJT, the fastest serial chain method.
Streaming execution at trillion scale (Version 4). The tree's rank locality lets windows of $m!$ consecutive lines be emitted without ever materializing the full list, under a provable block-size law $m! \cdot \Pi_{\max} < 2^{62}$ that makes every 64-bit window sum overflow-safe, with window partials reduced exactly in arbitrary-precision integers. Measured: the exact $14 \times 14$ determinant — 87.2 billion terms — on a free Tesla T4 in 194 MB of working memory (materialization would need 1.2 TB: a ~6,300× reduction); and a fused register-resident CUDA kernel on one NVIDIA B300 summing 20,922,789,888,000 terms ($n = 16$) exactly in 361 seconds at a flat $57.9 \times 10^{9}$ lines/s — every value certified equal to independent exact fraction-free Bareiss elimination. Horizons are reported as measurements, not promises: $n = 17$ at 1.7 h, $n = 18$ at 30.7 h, $n = 19$ at 584 h on the same device.

Why It Matters

The classical lexicographic approach costs $O(n^2 \cdot n!)$ total. berkeDet costs $O(n \cdot n!)$ — a factor of $n$ faster — matching the Steinhaus–Johnson–Trotter algorithm, the fastest non-lexicographic method, while keeping lexicographic order. And unlike every classical method, its structure is a tree rather than a chain, so it alone can exploit vector and parallel hardware.

berkeDet is the first method to combine the SJT-class total cost, lexicographic output order, and sublinear-span parallel structure in a single construction.

Comparison with Existing Methods

Method Tperm Tsign Total Lex. Sort-free Parallel
Naive lex. + inversion count $O(n \log n)$ $O(n^2)$ $O(n^2 \cdot n!)$ Yes No No
Narayana + inversion count $O(n)$ $O(n^2)$ $O(n^2 \cdot n!)$ Yes No* No
Narayana + merge-sort sign $O(n)$ $O(n \log n)$ $O(n \log n \cdot n!)$ Yes No* No
Narayana + $O(1)$ parity flip $O(n)$ $O(1)$ $O(n \cdot n!)$ Yes No* No
SJT + sign flip $O(n)$ $O(1)$ $O(n \cdot n!)$ No Yes No
Heap + bookkeeping $O(1)$ amort. $O(1)$ amort. $O(n!)$ No Yes No
berkeDet (this work) $O(n)$ amort. $O(1)$ amort. $O(n \cdot n!)$ Yes Yes Yes

*Narayana Pandita replaces sorting with suffix reversal — a non-trivial optimization that still requires per-step pivot scanning, swapping, and reversal.

Abstract (Version 4)

Every classical permutation generator — the lexicographic steppers (naive, Narayana Pandita) and the swap-based methods (Steinhaus–Johnson–Trotter, Heap) — is an incremental chain: permutation $r+1$ is computed from the value of permutation $r$, so the critical path is $\Omega(n!)$ and vector or parallel hardware is given no independent work. We present a compositional alternative built purely from block replication and index mapping. Its two subroutines, meryemPer (all $n!$ permutations, lexicographic order, $O(n \cdot n!)$ work, no sorting, reversal, or scanning) and meryemSign (all $n!$ signs, $\Theta(n!)$ work, no inversion counting), form a factorial tree in which every element of a layer is a pure function of one element of the previous layer; in the work–span model both have span $O(n)$, giving parallelism $\Theta(n!)$. To our knowledge meryemPer is the first inherently data-parallel lexicographic permutation generator: a single-core vectorized realization already outruns the C-implemented itertools chain by up to 6.4×. We then develop a streaming execution scheme that exploits the tree's rank locality: fixed chunks of $m!$ lexicographically consecutive lines are emitted through a block-size law $m! \cdot \Pi_{\max} < 2^{62}$ that makes every 64-bit chunk sum provably overflow-safe, with chunk partials reduced exactly in arbitrary-precision integers. Applied to the Leibniz determinant as a certified stress test, the scheme computes the exact $14 \times 14$ determinant (87.2 billion terms) on a free Tesla T4 in 194 MB of working memory — a 6,300× reduction over materialization — and, with a fused register-resident kernel on one NVIDIA B300, sums 20,922,789,888,000 terms ($n = 16$) exactly in 361 s at a flat $57.9 \times 10^{9}$ lines/s, every value certified equal to the independent fraction-free Bareiss computation, while LU floating-point error drifts from $10^{-16}$ to $10^{-15}$ over the same range. Measured horizons are reported honestly: $n = 17$ at 1.7 h, $n = 18$ at 30.7 h, $n = 19$ at 584 h on the same device. Full text and archive: Version 4 paper (DOI: 10.5281/zenodo.21709734).

Scope and Applicability

Like all Leibniz-based methods, berkeDet has factorial time complexity and is intended for exact determinant computation of small to moderate matrices, symbolic algebra, and educational contexts — not as a replacement for $O(n^3)$ numerical methods such as LU decomposition. The contribution is the most efficient known implementation of the Leibniz formula in lexicographic order — without sorting, reversal, or per-permutation sign computation — and the only one whose structure admits vector and parallel execution.

Lexicographic order supports reproducible testing, canonical ordering in symbolic algebra, teaching, and rank-partitioned distributed evaluation of the Leibniz sum — now backed by the span-$O(n)$ analysis.

Verification

Signs verified element-by-element through order 10 (all 3,628,800 at $n = 10$, three independent ways); permutations verified row-by-row through order 9, with random-rank spot checks beyond; determinants exact against numpy.linalg.det through order 10. All scripts are on the Resources page.

View the Algorithm →     Python Package →     View Resources →     View Timeline →

♥ Support This Research ♥