ah-comb.H File Reference

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

#include <htlist.H>
#include <tpl_dynDlist.H>
#include <tpl_dynArray.H>
#include <tpl_array.H>
#include <tpl_dynSetTree.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)

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).
• Check for existence or universality (exists_perm, all_perm).

Note

"Permutation" in this context means the cartesian product of the input lists, not mathematical permutations of a set.

Author

Leandro Rabindranath León

Definition in file ah-comb.H.