ah-comb.H File Reference

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

#include <algorithm>
#include <bit>
#include <cstdint>
#include <limits>
#include <numeric>
#include <htlist.H>
#include <tpl_dynDlist.H>
#include <tpl_dynArray.H>
#include <tpl_array.H>
#include <tpl_dynSetTree.H>
#include <ahFunction.H>
#include <ahSort.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)
	Transpose a matrix represented as a list of lists.
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)
	Traverse all the possible permutations that can be done of a list of lists and on each permutation performs an operation.
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)
	Enumerate all k-combinations of an Array<T> in lexicographic index order.
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 functions to:

• Transpose matrices represented as nested containers (transpose, in_place_transpose).
• Enumerate permutations (cartesian products) from a list of lists (traverse_perm, for_each_perm, build_perms).
• Build unique sorted combinations (build_combs).
• Fold over permutations (fold_perm).
• Count permutations (perm_count).
• Generate next lexicographic permutations on arrays (next_permutation).
• Generate k-combinations by index progression (next_combination_indices).
• Generate fixed-popcount bitmask combinations (next_combination_mask).
• Enumerate materialized k-combinations (for_each_combination, build_combinations).
• Count combinations with overflow checks (combination_count).
• Check for existence or universality (exists_perm, all_perm).

Note

traverse_perm/for_each_perm/build_perms use "permutation" in the cartesian-product sense. next_permutation is the classical lexicographic permutation of a single sequence.

Author

Leandro Rabindranath León

Definition in file ah-comb.H.