File Combinatorics.h

↰ Parent directory (ADS/numeric)

The examples of the introduction and of section 13.4 of chapter 13:

Definition (ADS/numeric/Combinatorics.h)

Detailed Description

  • binomial( n , k ) by its recursive definition :math:` C( n , k ) = C( n - 1 , k - 1 ) + C( n - 1 , k ) , whose calls are as many as :math: 2 C( n , k ) - 1 `, and tartaglia(), the triangle of Tartaglia of all the C( m , k ), m <= n, in Theta( n^2 ) time, each then read in O( 1 );

  • fibonacci(), F_0 = F_1 = 1 and F_n = F_{n-1} + F_{n-2}, with a vector of n places and with three variables, O( n ) time and O( 1 ) space, while the recursion makes about :math:` 1.6^n ` calls; FibonacciCache keeps the numbers already computed between the calls, in a mutable member, so that a number already asked for costs O( 1 ) and a new one only the steps from the largest one known;

  • beyond the book, factorial() and factorialRec(), the iterative and the recursive realization of the same specification (the functional abstraction), and binomialByFactorials(), :math:` n! / ( k! ( n - k )! ) `, which overflows as soon as n! does, i.e., for n > 20, while the recursion and the triangle reach n = 67.

The contracts [see File Contract.h]: the results fit in 64 bits, i.e., 0 <= k <= n <= 67 for binomial() and the triangle, 0 <= n <= 92 for the numbers of Fibonacci, 0 <= n <= 20 for the factorial and for binomialByFactorials(). The functions are defined in Combinatorics.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/numeric/impl/Combinatorics.tpp

  • cstddef

  • cstdint

  • vector

Namespaces

Classes

Functions