Combinatorics utilities: permutations, combinations, and matrix transposition. More...

#include <algorithm>
#include <bit>
#include <cstdint>
#include <limits>
#include <numeric>
#include <ah-errors.H>
#include <htlist.H>
#include <tpl_dynDlist.H>
#include <tpl_dynArray.H>
#include <tpl_array.H>
#include <tpl_dynSetTree.H>

Include dependency graph for ah-comb.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<typename T >
DynList< DynList< T > >	Aleph::transpose (const DynList< DynList< T > > &l)
	*‍/

template<template< typename > class C, typename T >
void	Aleph::in_place_transpose (C< C< T > > &l)
	In-place transpose of a rectangular matrix stored as a nested container.

template<typename T >
void	Aleph::in_place_transpose (DynList< DynList< T > > &l)
	In-place transpose of a matrix stored as `DynList<DynList<T>>`.

template<typename T , class Op >
bool	Aleph::traverse_perm (const DynList< DynList< T > > &l, Op &op)
	*‍/

template<typename T , class Op >
bool	Aleph::traverse_perm (const DynList< DynList< T > > &l, Op &&op)

template<typename T , class Op >
void	Aleph::for_each_perm (const DynList< DynList< T > > &l, Op &op)
	Apply a procedure to every permutation produced by `traverse_perm`.

template<typename T , class Op >
void	Aleph::for_each_perm (const DynList< DynList< T > > &l, Op &&op)

template<typename T >
DynList< DynList< T > >	Aleph::build_perms (const DynList< DynList< T > > &l)
	Materialize all permutations from a list of lists.

template<typename T >
DynList< DynList< T > >	Aleph::build_combs (const DynList< DynList< T > > &l)
	Build the set of unique combinations from a list of lists.

template<typename T , typename Tc , class Op = Dft_Fold_Op<Tc, T>>
T	Aleph::fold_perm (const T &init, const DynList< DynList< Tc > > &l, Op &op)
	Left-fold over all permutations.

template<typename T , typename Tc , class Op = Dft_Fold_Op<Tc, T>>
T	Aleph::fold_perm (const T &init, const DynList< DynList< Tc > > &l, Op &&op)

template<typename T >
size_t	Aleph::perm_count (const DynList< DynList< T > > &l)
	Count the total number of permutations from a list of lists.

template<typename T , class Pred >
bool	Aleph::exists_perm (const DynList< DynList< T > > &l, Pred &pred)
	Check if any permutation satisfies a predicate.

template<typename T , class Pred >
bool	Aleph::exists_perm (const DynList< DynList< T > > &l, Pred &&pred)

template<typename T , class Pred >
bool	Aleph::all_perm (const DynList< DynList< T > > &l, Pred &pred)
	Check if all permutations satisfy a predicate.

template<typename T , class Pred >
bool	Aleph::all_perm (const DynList< DynList< T > > &l, Pred &&pred)

template<typename T , class Pred >
bool	Aleph::none_perm (const DynList< DynList< T > > &l, Pred &pred)
	Check if no permutation satisfies a predicate.

template<typename T , class Pred >
bool	Aleph::none_perm (const DynList< DynList< T > > &l, Pred &&pred)

template<typename T , class Pred >
DynList< DynList< T > >	Aleph::filter_perm (const DynList< DynList< T > > &l, Pred &pred)
	Filter permutations that satisfy a predicate.

template<typename T , class Pred >
DynList< DynList< T > >	Aleph::filter_perm (const DynList< DynList< T > > &l, Pred &&pred)

template<typename R , typename T , class Op >
DynList< R >	Aleph::map_perm (const DynList< DynList< T > > &l, Op &op)
	Transform each permutation via a mapping operation.

template<typename R , typename T , class Op >
DynList< R >	Aleph::map_perm (const DynList< DynList< T > > &l, Op &&op)

template<typename T , class Compare = Aleph::less<T>>
bool	Aleph::next_permutation (Array< T > &a, Compare cmp=Compare(), const bool reset_on_last=true)
	Compute the next lexicographic permutation of an `Array`.

template<typename T , class Compare = Aleph::less<T>>
bool	Aleph::next_permutation (DynArray< T > &a, Compare cmp=Compare(), const bool reset_on_last=true)

size_t	Aleph::combination_count (size_t n, size_t k)
	Compute `n choose k` with overflow checks.

bool	Aleph::next_combination_indices (Array< size_t > &idx, const size_t n, const bool reset_on_last=true)
	Advance an index-combination `[i0 < i1 < ... < i(k-1)]` to the next one.

bool	Aleph::next_combination_indices (DynArray< size_t > &idx, const size_t n, const bool reset_on_last=true)

uint64_t	Aleph::first_combination_mask (const size_t k)
	Build the first k-of-64 combination mask (`k` low bits set).

bool	Aleph::next_combination_mask (uint64_t &mask, const size_t n, const bool reset_on_last=true)
	Advance a fixed-popcount bitmask to the next combination (Gosper hack).

template<typename T , class Op >
bool	Aleph::for_each_combination (const Array< T > &values, const size_t k, Op &&op)
	*‍/

template<typename T , class Op >
bool	Aleph::for_each_combination (const DynArray< T > &values, const size_t k, Op &&op)

template<typename T >
Array< Array< T > >	Aleph::build_combinations (const Array< T > &values, const size_t k)
	Materialize all k-combinations of `Array<T>`.

template<typename T >
Array< Array< T > >	Aleph::build_combinations (const DynArray< T > &values, const size_t k)

template<std::unsigned_integral T>
constexpr T	Aleph::bin_to_gray (const T n) noexcept
	Convert a binary number to its Gray code representation.

template<std::unsigned_integral T>
constexpr T	Aleph::gray_to_bin (T g) noexcept
	Convert a Gray code number to its binary representation.

Array< uint32_t >	Aleph::build_gray_code (const size_t n)
	Generate the sequence of n-bit Gray codes.

Detailed Description

Combinatorics utilities: permutations, combinations, and matrix transposition.

This header provides a comprehensive set of tools for combinatorial generation and manipulation:

Permutations (Cartesian Product): Functions to traverse and build all possible sequences formed by picking one element from each of a list of input lists (e.g., {1,2} x {a,b} -> {(1,a), (1,b), (2,a), (2,b)}).
Lexicographic Permutations: Linear-time generation of the next permutation of a single sequence (STL-style next_permutation).
Combinations: Generate k-subsets of a set of n elements, using either index-based progression or bitmask-based (Gosper's hack).
Binomial Coefficients: Computation of \(\binom{n}{k}\)with overflow protection.
Gray Codes: Functions to convert between binary and Gray code and to generate full Gray code sequences.
Matrix Transposition: Utilities to transpose matrices represented as nested containers (lists or arrays).

Note: Terminology Note: traverse_perm/for_each_perm refer to the Cartesian product of multiple lists. next_permutation refers to reordering elements of a single container.

Author: Leandro Rabindranath Leon

Definition in file ah-comb.H.

Namespaces

Functions

Detailed Description