berkeDet for Python

On this page: Install · The three tools · Examples · Why it is fast · Benchmarks · Compare it yourself · License · Cite

Install

pip install berkeDet

Ready-made for Python 3.9 to 3.14 on Windows, macOS (Apple Silicon and Intel) and Linux (x86-64 and ARM). The only requirement is NumPy, which pip installs for you.

The Three Tools

Use them together or on their own:

• meryemPer(items, start=None, stop=None) — all permutations in lexicographic order, as one NumPy array. An integer n gives the permutations of 0, 1, …, n−1; a string, list or array gives the permutations of its items, in exactly the order of itertools.permutations. Up to 20 items. start and stop return any range of ranks directly.
• meryemSign(items, start=None, stop=None) — the sign (+1 or −1) of each of those permutations, in the same order, built without counting inversions.
• berkeDet(matrix) — the determinant by the Leibniz formula, streamed through meryemPer and meryemSign: exact for integers of any size and for fractions, float64 for floating-point matrices.

Examples

Every output below is exactly what the code prints. Run the examples in order: the first one imports the three tools.

The three tools

from berkeDet import meryemPer, meryemSign, berkeDet

print(meryemPer(3))     # all 3! = 6 permutations of 0, 1, 2
print(meryemSign(3))    # their signs, in the same order
print(berkeDet([[6, 1, 1], [4, -2, 5], [2, 8, 7]]))   # exact determinant

[[0 1 2]
 [0 2 1]
 [1 0 2]
 [1 2 0]
 [2 0 1]
 [2 1 0]]
[ 1 -1 -1  1  1 -1]
-306

Prefer counting from 1, as in the paper? meryemPer(3) + 1 gives [1, 2, 3], [1, 3, 2], …

Any items, in the order of itertools

import itertools

P = meryemPer("ABC")
print(["".join(row) for row in P])
print(P.tolist() == [list(p) for p in itertools.permutations("ABC")])

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
True

Millions at once

One call, one array: 39,916,800 rows of 11 bytes each (439 MB) — no Python object per permutation.

P = meryemPer(11)       # all 39,916,800 permutations of 0..10
print(P.shape, P.dtype)
print(P[0], P[-1])      # the first and the last

(39916800, 11) uint8
[ 0  1  2  3  4  5  6  7  8  9 10] [10  9  8  7  6  5  4  3  2  1  0]

Jump straight to any rank

Twenty items have 20! ≈ 2.4 × 10¹⁸ permutations. start and stop compute any stretch of that list directly, without generating the permutations before it — here the three that start at rank 10¹⁸. A million at a time takes milliseconds.

rank = 10**18
print(meryemPer(20, start=rank, stop=rank + 3))    # three permutations of 20 items
print(meryemSign(20, start=rank, stop=rank + 3))   # and their signs

[[ 8  4  3 10 16  7 13  6 17  9 18 12  2  5 19  1 14 15  0 11]
 [ 8  4  3 10 16  7 13  6 17  9 18 12  2  5 19  1 14 15 11  0]
 [ 8  4  3 10 16  7 13  6 17  9 18 12  2  5 19  1 15  0 11 14]]
[-1  1  1]

The Leibniz formula in three lines

meryemPer and meryemSign list the permutations and their signs in the same order, so they combine directly with NumPy:

import numpy as np

A = np.array([[6, 1, 1], [4, -2, 5], [2, 8, 7]])
P = meryemPer(3)                          # one permutation per row
s = meryemSign(3)                         # one sign per row
terms = s * A[[0, 1, 2], P].prod(axis=1)  # sign * a[0][p0] * a[1][p1] * a[2][p2]
print(terms, terms.sum())

[ -84 -240  -28   10   32    4] -306

Exact, whatever the numbers

Integer matrices give the exact integer determinant: while the entries are moderate the sum runs in C with an exact 128-bit accumulator, beyond that in Python’s unbounded integers. Fractions stay exact, and floating-point matrices are computed in float64.

from fractions import Fraction

print(berkeDet([[2**70, 1], [3, 2**70]]))                    # huge integers: exact
print(berkeDet([[Fraction(1, 2), 1], [1, Fraction(1, 3)]]))  # fractions: exact
print(berkeDet([[0.5, 1.5], [2.0, 4.0]]))                    # floats: float64

1393796574908163946345982392040522594123773
-5/6
-1.0

Asking for all 13! permutations at once would need 81 GB, so meryemPer stops with a clear MemoryError instead of exhausting your memory (the limit is 8 GiB; change it with max_bytes). Use start and stop to work through such lists in windows.

Why It Is So Fast

Every classical generator — itertools.permutations, C++’s std::next_permutation (Narayana Pandita’s algorithm), Heap’s algorithm, Steinhaus–Johnson–Trotter — is a chain: each permutation is computed from the one before it. A chain is serial by nature; a second core cannot start on permutation one million before the first 999,999 are done.

meryemPer builds the whole list for n items from the list for n − 1 items, in n independent blocks. Block f starts with f and continues with the previous list, every value x replaced by x + (x ≥ f). meryemSign uses the same blocks: block f carries the previous signs multiplied by (−1)^f.

Because the blocks never wait for each other, the work runs as long, contiguous operations on bytes — exactly what compilers turn into vector (SIMD) instructions — and it splits across all CPU cores. In the default column layout each position of the result is stored contiguously, just as the blocks are written, which is why it is the fastest layout. And where itertools hands out a Python tuple for every permutation, meryemPer writes straight into a single NumPy array. The Algorithm page explains the construction in full.

Benchmarks

All permutations of 11 items (39,916,800) in lexicographic order, as a NumPy array. Median of 5 runs of benchmarks/bench.py from the GitHub repository, on a 2-core Intel Xeon 2.10 GHz cloud machine, Python 3.11, NumPy 2.4.

The machine is shared, so the same measurement varies between runs. Across repeated runs with 11 items, against the C chain, the default column layout measured 2.6–3.9× on one core and 4.3–5.9× on two; the row layout measured 0.8–1.2× on one core (about the speed of a well-written chain generator) and 1.4–2.1× on two. The chain generator is written in the same C as berkeDet, so the comparison is between methods, not languages.

Most of the gap to itertools is Python’s cost of creating a tuple per permutation. Yet even with that cost removed — itertools only looping, storing nothing, took 0.36–0.43 s — meryemPer’s complete array is ready 3–5× sooner. Also measured: all 479,001,600 signs of 12 items in 0.13 s, and the exact determinant of a 12 × 12 integer matrix (479 million Leibniz terms) in 1.1 s.

These are measurements of the compiled package. The figures in the paper (for example 6.4× over itertools) were measured with a pure-NumPy realization of the same algorithm; compiled C widens the margins. Scaling beyond two cores has not been measured here — run the comparison below on your own machine.

Compare It Yourself

Download compare_itertools.py and run it. It checks that itertools and meryemPer produce identical arrays, times both, and then jumps to rank 10¹⁸ of 20 items. Without the 11 it runs a quick 10-item test; the 11-item run takes about a minute and 1.5 GB of memory (itertools is the slow part).

pip install berkeDet
python compare_itertools.py 11

The script

"""meryemPer vs itertools.permutations: same permutations, same order, timed.

    pip install berkeDet
    python compare_itertools.py        # 10 items:  3,628,800 permutations
    python compare_itertools.py 11     # 11 items: 39,916,800 permutations
                                       # (about a minute and 1.5 GB of memory)

Both methods list every permutation of 0, 1, ..., n-1 in lexicographic order.
The script first checks that the two results are identical, then times them.
berkeDet is free for noncommercial use: https://detsignper.org/python.html
"""
import collections
import itertools
import math
import os
import platform
import sys
import time

import numpy as np

import berkeDet
from berkeDet import meryemPer


def best_time(fn, repeat=3):
    """Best wall-clock time of `repeat` runs, in seconds."""
    best = float("inf")
    for _ in range(repeat):
        start = time.perf_counter()
        fn()
        best = min(best, time.perf_counter() - start)
    return best


def itertools_array(n):
    """itertools.permutations, collected into the same NumPy array."""
    flat = itertools.chain.from_iterable(itertools.permutations(range(n)))
    count = math.factorial(n)
    return np.fromiter(flat, dtype=np.uint8, count=count * n).reshape(count, n)


def itertools_loop_only(n):
    """itertools.permutations, only looped over: nothing is kept.
    (A deque of length 0 consumes the iterator at full C speed.)"""
    collections.deque(itertools.permutations(range(n)), maxlen=0)


n = int(sys.argv[1]) if len(sys.argv) > 1 else 10
if not 2 <= n <= 11:
    sys.exit("Choose n from 2 to 11 (12 items would need about 6 GB per array).")
cores = os.cpu_count() or 1
print(f"berkeDet {berkeDet.__version__} | Python {platform.python_version()} | "
      f"NumPy {np.__version__} | {cores} CPU cores")
print(f"\nAll {math.factorial(n):,} permutations of {n} items, lexicographic order")

# 1. Same result?
same = np.array_equal(itertools_array(n), meryemPer(n))
print("Identical results from itertools and meryemPer:", "YES" if same else "NO")
if not same:
    sys.exit(1)

# 2. Timings
rows = [
    ("itertools.permutations -> NumPy array", lambda: itertools_array(n)),
    ("itertools.permutations, loop only (no array)", lambda: itertools_loop_only(n)),
    ("meryemPer, 1 core", lambda: meryemPer(n, threads=1)),
    (f"meryemPer, all {cores} cores", lambda: meryemPer(n)),
]
times = {}
print(f"\n{'method':<46}{'seconds':>10}")
for label, fn in rows:
    times[label] = best_time(fn)
    print(f"{label:<46}{times[label]:>10.4f}")

ours = times[rows[3][0]]
print(f"\nmeryemPer built the array {times[rows[0][0]] / ours:.0f}x faster than itertools,")
print(f"and {times[rows[1][0]] / ours:.1f}x faster than itertools can merely loop over the permutations.")

# 3. Direct access by rank: a million permutations of 20 items, from rank 10**18
rank = 10**18
start = time.perf_counter()
window = meryemPer(20, start=rank, stop=rank + 1_000_000)
seconds = time.perf_counter() - start
print(f"\n1,000,000 permutations of 20 items starting at rank 10^18, in {seconds:.3f} s:")
print("  first:", window[0].tolist())
print("  last: ", window[-1].tolist())

# itertools can only start from the beginning: measure its speed on 20 items
start = time.perf_counter()
collections.deque(itertools.islice(itertools.permutations(range(20)), 2_000_000), maxlen=0)
per_second = 2_000_000 / (time.perf_counter() - start)
years = rank / per_second / (365.25 * 24 * 3600)
print(f"itertools would first have to step through 10^18 permutations:"
      f" about {years:,.0f} years at its speed measured here.")

berkeDet 1.0.0 | Python 3.14.7 | NumPy 2.5.3 | 2 CPU cores

All 39,916,800 permutations of 11 items, lexicographic order
Identical results from itertools and meryemPer: YES

method                                           seconds
itertools.permutations -> NumPy array            10.7087
itertools.permutations, loop only (no array)      0.3824
meryemPer, 1 core                                 0.1402
meryemPer, all 2 cores                            0.0809

meryemPer built the array 132x faster than itertools,
and 4.7x faster than itertools can merely loop over the permutations.

1,000,000 permutations of 20 items starting at rank 10^18, in 0.009 s:
  first: [8, 4, 3, 10, 16, 7, 13, 6, 17, 9, 18, 12, 2, 5, 19, 1, 14, 15, 0, 11]
  last:  [8, 4, 3, 10, 16, 7, 13, 6, 17, 11, 1, 9, 0, 18, 15, 14, 5, 2, 19, 12]
itertools would first have to step through 10^18 permutations: about 413 years at its speed measured here.

Above: the output of python compare_itertools.py 11 on a 2-core cloud machine (Intel Xeon, Python 3.14, NumPy 2.5). Your numbers will differ with your hardware.

When itertools Is the Better Choice

If you walk through permutations one at a time in a Python loop and do Python work on each, the loop itself is the bottleneck, and itertools.permutations — simple and lazy — is the right tool. berkeDet is for code that consumes whole arrays (NumPy, GPUs, compiled code), for signs, and for jumping to any rank. For determinants of large numerical matrices, an O(n³) method such as numpy.linalg.det is the right tool: the Leibniz formula has n! terms, and berkeDet gives exact answers for small matrices.

License

berkeDet is free for noncommercial use under the PolyForm Noncommercial License 1.0.0: personal study, research and experiment, teaching, hobby projects, and use by educational institutions, public research organizations, charities and government institutions. Any commercial use — for example in a company’s products, services or internal work — requires a separate commercial license from the authors: gulmenberkemeryem@gmail.com. The license text is authoritative; this summary is only a guide.

Cite

If you use berkeDet in your work, please cite the paper:

Gülmen, B., Gülmen, M., & Gülmen, Ö. (2026).
berkeDet: Data-Parallel Lexicographic Permutation Generation and
Streaming Exact Determinant Evaluation via Block Replication and
Index Mapping (Version 4).
Zenodo. https://doi.org/10.5281/zenodo.21709734

PyPI →     GitHub →     The Algorithm →