File Enumeration.h

↰ Parent directory (ADS/backtrack)

The enumeration of the feasible solutions by backtrack (section 16.2): a solution is a vector S[ 0 .

Definition (ADS/backtrack/Enumeration.h)

Detailed Description

. n - 1 ], each S[ i ] taken from the choices allowed by S[ 0 .. i - 1 ]; each choice is tried, the solutions are processed, and the search goes on recursively from S[ 0 .. i ], a depth first visit of the tree of the choices. The processing returns true to stop at the first solution.

  • subsets(), the subsets of k of the n items, by the choices in or out, pruned when k items are in or when the items left are too few;

  • permutations() and derangements(), each item not chosen yet, the latter not in its own place (exercises 16.2 and 16.3);

  • subsetSum(), the subsets of positive items of sum k, pruned when the sum exceeds k (exercise 16.4).

Each calls f( S ) on the solutions, in increasing order of the choices, and returns how many there are, or stops when f returns true. The subsets of k items are :math:` binom{n}{k} = n! / ( k! ( n - k )! ) ` (the text writes n! / ( n - k )!, the number of their orderings).

The contracts [see File Contract.h]: n and k are not negative, and the items of subsetSum() are positive. The operations are defined in Enumeration.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 16.2 and exercises 16.2-16.4, https://algoritmicamente.it/materiali/libro/capitoli/cap16.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions