FLINT3.7.0-dev
/
Module · 14 functions

perm.h

#include <flint/perm.h>

A permutation \pi of \{0, 1, \ldots, n - 1\} is stored as an array vec of n slong entries with vec[i] = \pi(i). The identity is {0, 1, ..., n - 1}. Such arrays are used throughout FLINT, notably for the row permutations returned by LU decompositions and echelon forms of matrices (for example nmod_mat_lu and fmpz_mat_fflu) and for permuting vectors (_gr_vec_permute).

All functions have a leading underscore: they take a plain array and its length n, and do not check that the arrays hold permutations. A permutation is created with _perm_init, or in any array of n slong entries with _perm_one. Composition is written as for functions: (\pi_1 \circ \pi_2)(i) = \pi_1(\pi_2(i)), so \pi_2 is applied first. Unless stated otherwise, output and input arrays may be the same.

Permutations are printed with flint_printf("%{slong*}", vec, n); the older _perm_print has been removed.

Memory management#

slong * _perm_init(slong n)

Returns a newly allocated array of length n holding the identity permutation. It must be freed with _perm_clear.

void _perm_clear(slong * vec)

Frees an array allocated by _perm_init.

Assignment and inverse#

void _perm_set(slong * res, const slong * vec, slong n)

Copies the permutation vec to res.

void _perm_one(slong * vec, slong n)

Sets vec to the identity permutation.

void _perm_inv(slong * res, const slong * vec, slong n)

Sets res to the inverse permutation of vec, so that res[vec[i]] = i. If res and vec are the same array, a temporary copy is allocated.

Comparison#

slong _perm_equal(const slong * vec1, const slong * vec2, slong n)

Returns 1 if the two arrays have the same n entries, and 0 otherwise.

slong _perm_is_one(const slong * vec, slong n)

Returns 1 if vec is the identity permutation, and 0 otherwise.

Composition#

void _perm_compose(slong * res, const slong * vec1, const slong * vec2, slong n)

Sets res to \pi_1 \circ \pi_2, where vec1 and vec2 hold \pi_1 and \pi_2; that is, res[i] = vec1[vec2[i]]. Any aliasing is allowed.

void _perm_compose_inv1(slong * res, const slong * vec1, const slong * vec2, slong n)

Sets res to \pi_1^{-1} \circ \pi_2, that is, res[i] = \pi_1^{-1}(\pi_2(i)), without forming \pi_1^{-1} separately when res is vec2. Any aliasing is allowed.

void _perm_compose_inv2(slong * res, const slong * vec1, const slong * vec2, slong n)

Sets res to \pi_1 \circ \pi_2^{-1}, that is, res[vec2[i]] = vec1[i]. Any aliasing is allowed.

Parity#

int _perm_parity(const slong * vec, slong n)

Returns the parity of the permutation: 0 if it is even and 1 if it is odd. It counts the cycles c and returns (n - c) \bmod 2, using a temporary array of n flags.

Random permutations#

int _perm_randtest(slong * vec, slong n, flint_rand_t state)

Sets vec to a uniformly random permutation of length n, generated by the Fisher–Yates shuffle [Dur1964; Knu1997, §3.4.2], and returns its parity.

Enumeration#

The two functions below step through all n! permutations. Enumerating permutations compares them and has an example.

int _perm_next_lex(slong * res, slong n)

Replaces res by the next permutation in lexicographic order and returns 1, or returns 0 and leaves res unchanged if res is the last permutation (n - 1, \ldots, 1, 0). Starting from the identity, the calls return 1 exactly n! - 1 times.

Full documentation
int _perm_next_heap(slong * res, slong n, slong * stack)

Replaces res by the next permutation in the order of Heap's algorithm [Hea1963] and returns 1, or returns 0 when all permutations have been visited. Consecutive permutations differ by one transposition. The array stack of length n holds the iteration state; the enumeration starts with stack set to zeros and res set to any permutation (usually the identity). For n \le 1 there is only one permutation, and the function returns 0 at once without accessing the arrays.

Full documentation

References#

  • [Dur1964] R. Durstenfeld. Algorithm 235: Random permutation. Communications of the ACM 7(7), 420, 1964.
  • [Knu1997] Knuth, D. E. The Art of Computer Programming, volume 2: Seminumerical algorithms, 1997
  • [Hea1963] B. R. Heap. Permutations by interchanges. The Computer Journal 6(3), 293–298, 1963.
Cite this page

The FLINT team, “perm.h (module overview),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/perm/index.html (generated 2026-10-20).