gpmp::Comb Class Reference

A class providing various combinatorial functions and algorithms. More...

#include <comb.hpp>

Public Member Functions
int64_t	permutation (int n, int r)
	Calculate the number of permutations (nPr) More...
int64_t	combination (int n, int r)
	Calculate the number of combinations (nCr) More...
int64_t	binom_coeff (int n, int r)
	Calculate the binomial coefficient (n choose r) More...
int64_t	factorial (int n)
	Calculate the factorial of a number. More...
std::vector< std::vector< int > >	partitions (int n)
	Generate all partitions of a positive integer n. More...
std::vector< int64_t >	bell_num (int n)
	Calculate the Bell numbers. More...
int64_t	stirling_num (int n, int k)
	Calculate the Stirling number of the second kind. More...
std::vector< int >	gray_code (int n)
	Generate the Gray code sequence of length n. More...
int64_t	subfactorial (int n)
	Calculate the subfactorial (!n) or derangement of n. More...
int64_t	subsequences (int n, int k)
	Calculate the number of subsequences of length k from n items. More...
std::vector< std::vector< int > >	partition_distinct (int n)
	Generate all distinct partitions of a positive integer n. More...
std::vector< std::vector< int > >	compositions (int n)
	Generate all compositions of a positive integer n. More...
int64_t	dyck_words (int n)
	Calculate the number of Dyck words of length 2n. More...
std::vector< std::string >	gen_dyck_words_until (int n)
	Generate Dyck words up to length n. More...
int64_t	necklaces (int n, int k)
	Calculate the number of necklaces of length n with k colors. More...
int	phi (int n)
	Calculate Euler's totient function (φ) More...
std::vector< std::vector< int > >	generateNecklaces (int n, int k)
	Generate all necklaces of length n with k colors. More...
int64_t	lyndonWords (int n)
	Calculate the number of Lyndon words of length n. More...
std::vector< std::string >	generateLyndonWords (int n)
	Generate all Lyndon words of length n. More...
void	generatePartitions (int n, int max, std::vector< int > &partition, std::vector< std::vector< int >> &result)
	Generate partitions of a positive integer. More...
void	gen_partition_distinct (int n, int max, std::vector< int > &partition, std::vector< std::vector< int >> &result)
	Generate distinct partitions of a positive integer. More...
void	gen_compositions (int n, int max, std::vector< int > &composition, std::vector< std::vector< int >> &result)
	Generate compositions of a positive integer. More...
void	gen_dyck_words (std::string prefix, int open, int close, std::vector< std::string > &dyck_words)
	Generate Dyck words. More...
void	gen_necklaces (std::vector< int > &necklace, int index, int n, int k, std::vector< std::vector< int >> &necklaces)
	Generate necklaces. More...
void	gen_lyndon_words (std::string prefix, int n, int max, std::vector< std::string > &lyndonWords)
	Generate Lyndon words. More...
std::vector< int >	divisors (int n)
	Calculate the divisors of a positive integer. More...
template<typename T >
std::vector< std::vector< T > >	permutations (const std::vector< T > &vec)
	Generate all permutations of a vector. More...
template<typename T >
std::vector< std::vector< T > >	combinations (const std::vector< T > &vec, int r)
	Generate all combinations of a vector. More...

Detailed Description

A class providing various combinatorial functions and algorithms.

Definition at line 47 of file comb.hpp.

Member Function Documentation

bell_num()

std::vector< int64_t > gpmp::Comb::bell_num

(

int

n

)

Calculate the Bell numbers.

Parameters

n	The number of Bell numbers to calculate

Returns

A vector of Bell numbers

Definition at line 99 of file comb.cpp.

                                           {
    std::vector<int64_t> bell(n + 1, 0);
    bell[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            bell[i] += binom_coeff(i - 1, j) * bell[j];
        }
    }
    return bell;
}

Referenced by main().

binom_coeff()

int64_t gpmp::Comb::binom_coeff	(	int	n,
		int	r
	)

Calculate the binomial coefficient (n choose r)

Parameters

n	The total number of items
r	The number of items to choose

Returns

The binomial coefficient

Definition at line 65 of file comb.cpp.

                                          {
    if (n < r)
        return 0;           // Invalid input
    r = std::min(r, n - r); // Optimization to reduce calculations
    std::vector<int64_t> dp(r + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = std::min(i, r); j > 0; --j) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[r];
}

Referenced by main().

combination()

int64_t gpmp::Comb::combination	(	int	n,
		int	r
	)

Calculate the number of combinations (nCr)

Parameters

n	The total number of items
r	The number of items to choose

Returns

The number of combinations

Definition at line 52 of file comb.cpp.

                                          {
    if (n < r)
        return 0;           // Invalid input
    r = std::min(r, n - r); // Optimization to reduce calculations
    int64_t result = 1;
    for (int i = 0; i < r; ++i) {
        result *= (n - i);
        result /= (i + 1);
    }
    return result;
}

Referenced by main().

combinations()

template<typename T >

std::vector<std::vector<T> > gpmp::Comb::combinations	(	const std::vector< T > &	vec,
		int	r
	)

Generate all combinations of a vector.

Template Parameters

T	The type of elements in the vector

Parameters

vec	The vector
r	The size of combinations

Returns

A vector of all combinations

Referenced by main().

compositions()

std::vector< std::vector< int > > gpmp::Comb::compositions

(

int

n

)

Generate all compositions of a positive integer n.

Parameters

n	The integer to compose

Returns

A vector of compositions

Definition at line 167 of file comb.cpp.

                                                      {
    std::vector<std::vector<int>> result;
    std::vector<int> composition;
    gen_compositions(n, n, composition, result);
    return result;
}

Referenced by main().

divisors()

std::vector< int > gpmp::Comb::divisors

(

int

n

)

Calculate the divisors of a positive integer.

Parameters

n	The integer

Returns

A vector of divisors

Definition at line 349 of file comb.cpp.

                                       {
    std::vector<int> divs;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            divs.push_back(i);
            if (i != n / i) {
                divs.push_back(n / i);
            }
        }
    }
    return divs;
}

dyck_words()

int64_t gpmp::Comb::dyck_words

(

int

n

)

Calculate the number of Dyck words of length 2n.

Parameters

n	The length parameter

Returns

The number of Dyck words

Definition at line 175 of file comb.cpp.

                                  {
    return binom_coeff(2 * n, n) / (n + 1);
}

Referenced by main().

factorial()

int64_t gpmp::Comb::factorial

(

int

n

)

Calculate the factorial of a number.

Parameters

n	The number

Returns

The factorial of n

Definition at line 80 of file comb.cpp.

                                 {
    if (n < 0)
        return 0; // Invalid input
    int64_t result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

Referenced by main().

gen_compositions()

void gpmp::Comb::gen_compositions	(	int	n,
		int	max,
		std::vector< int > &	composition,
		std::vector< std::vector< int >> &	result
	)

Generate compositions of a positive integer.

Parameters

n	The integer to compose
max	The maximum value in each composition
composition	The current composition being generated
result	The resulting vector of compositions

Definition at line 277 of file comb.cpp.

                                                                     {
    if (n == 0) {
        result.push_back(composition);
        return;
    }
 
    for (int i = std::min(n, max); i >= 1; --i) {
        composition.push_back(i);
        gen_compositions(n - i, i, composition, result);
        composition.pop_back();
    }
}

gen_dyck_words()

void gpmp::Comb::gen_dyck_words	(	std::string	prefix,
		int	open,
		int	close,
		std::vector< std::string > &	dyck_words
	)

Generate Dyck words.

Parameters

prefix	The current Dyck word prefix
open	The number of open parentheses remaining
close	The number of close parentheses remaining
dyck_words	The resulting vector of Dyck words

Definition at line 294 of file comb.cpp.

                                                                  {
    if (open == 0 && close == 0) {
        dyck_words.push_back(prefix);
        return;
    }
    if (open > 0) {
        gen_dyck_words(prefix + "(", open - 1, close, dyck_words);
    }
    if (close > open) {
        gen_dyck_words(prefix + ")", open, close - 1, dyck_words);
    }
}

gen_dyck_words_until()

std::vector< std::string > gpmp::Comb::gen_dyck_words_until

(

int

n

)

Generate Dyck words up to length n.

Parameters

n	The maximum length of Dyck words

Returns

A vector of Dyck words

Definition at line 180 of file comb.cpp.

                                                         {
    std::vector<std::string> dyck_words;
    gen_dyck_words("", n, n, dyck_words);
    return dyck_words;
}

Referenced by main().

gen_lyndon_words()

void gpmp::Comb::gen_lyndon_words	(	std::string	prefix,
		int	n,
		int	max,
		std::vector< std::string > &	lyndonWords
	)

Generate Lyndon words.

Parameters

prefix	The current Lyndon word prefix
n	The length of the Lyndon words
max	The maximum value in each Lyndon word
lyndonWords	The resulting vector of Lyndon words

Definition at line 328 of file comb.cpp.

                                                                     {
    if (static_cast<int>(prefix.size()) == n) {
        lyndonWords.push_back(prefix);
        return;
    }
 
    for (char c = (prefix.empty() ? 'a' : prefix.back() + 1);
         c <= 'z' && static_cast<int>(prefix.size()) < n;
         ++c) {
        if (n % (static_cast<int>(prefix.size()) + 1) == 0) {
            gen_lyndon_words(prefix + c, n, prefix.size() + 1, lyndonWords);
        } else {
            gen_lyndon_words(prefix + c, n, max, lyndonWords);
        }
    }
}

gen_necklaces()

void gpmp::Comb::gen_necklaces	(	std::vector< int > &	necklace,
		int	index,
		int	n,
		int	k,
		std::vector< std::vector< int >> &	necklaces
	)

Generate necklaces.

Parameters

necklace	The current necklace being generated
index	The current index in the necklace
n	The length of the necklace
k	The number of colors
necklaces	The resulting vector of necklaces

Definition at line 311 of file comb.cpp.

                                                                     {
    if (index == n) {
        necklaces.push_back(necklace);
        return;
    }
 
    for (int color = 1; color <= k; ++color) {
        necklace[index] = color;
        gen_necklaces(necklace, index + 1, n, k, necklaces);
    }
}

gen_partition_distinct()

void gpmp::Comb::gen_partition_distinct	(	int	n,
		int	max,
		std::vector< int > &	partition,
		std::vector< std::vector< int >> &	result
	)

Generate distinct partitions of a positive integer.

Parameters

n	The integer to partition
max	The maximum value in each partition
partition	The current partition being generated
result	The resulting vector of partitions

Definition at line 257 of file comb.cpp.

                                                                           {
    if (n == 0) {
        result.push_back(partition);
        return;
    }
 
    for (int i = std::min(n, max); i >= 1; --i) {
        if (std::find(partition.begin(), partition.end(), i) ==
            partition.end()) {
            partition.push_back(i);
            gen_partition_distinct(n - i, i, partition, result);
            partition.pop_back();
        }
    }
}

generateLyndonWords()

std::vector< std::string > gpmp::Comb::generateLyndonWords

(

int

n

)

Generate all Lyndon words of length n.

Parameters

n	The length of the Lyndon words

Returns

A vector of Lyndon words

Definition at line 233 of file comb.cpp.

                                                        {
    std::vector<std::string> lyndonWords;
    gen_lyndon_words("", n, n, lyndonWords);
    return lyndonWords;
}

Referenced by main().

generateNecklaces()

std::vector< std::vector< int > > gpmp::Comb::generateNecklaces	(	int	n,
		int	k
	)

Generate all necklaces of length n with k colors.

Parameters

n	The length of the necklace
k	The number of colors

Returns

A vector of necklaces

Definition at line 216 of file comb.cpp.

                                                                  {
    std::vector<std::vector<int>> necklaces;
    std::vector<int> necklace(n, 0);
    gen_necklaces(necklace, 0, n, k, necklaces);
    return necklaces;
}

Referenced by main().

generatePartitions()

void gpmp::Comb::generatePartitions	(	int	n,
		int	max,
		std::vector< int > &	partition,
		std::vector< std::vector< int >> &	result
	)

Generate partitions of a positive integer.

Parameters

n	The integer to partition
max	The maximum value in each partition
partition	The current partition being generated
result	The resulting vector of partitions

Definition at line 240 of file comb.cpp.

                                                                       {
    if (n == 0) {
        result.push_back(partition);
        return;
    }
 
    for (int i = std::min(n, max); i >= 1; --i) {
        partition.push_back(i);
        generatePartitions(n - i, i, partition, result);
        partition.pop_back();
    }
}

gray_code()

std::vector< int > gpmp::Comb::gray_code

(

int

n

)

Generate the Gray code sequence of length n.

Parameters

n	The number of bits in the sequence

Returns

A vector representing the Gray code

Definition at line 122 of file comb.cpp.

                                        {
    std::vector<int> gray;
    for (int i = 0; i < (1 << n); ++i) {
        gray.push_back(i ^ (i >> 1));
    }
    return gray;
}

Referenced by main().

lyndonWords()

int64_t gpmp::Comb::lyndonWords

(

int

n

)

Calculate the number of Lyndon words of length n.

Parameters

n	The length of the Lyndon word

Returns

The number of Lyndon words

Definition at line 224 of file comb.cpp.

                                   {
    int64_t result = 0;
    for (int d : divisors(n)) {
        result += phi(n / d);
    }
    return result;
}

Referenced by main().

necklaces()

int64_t gpmp::Comb::necklaces	(	int	n,
		int	k
	)

Calculate the number of necklaces of length n with k colors.

Parameters

n	The length of the necklace
k	The number of colors

Returns

The number of necklaces

Definition at line 188 of file comb.cpp.

                                        {
    if (n == 0)
        return 0;
    int64_t result = 0;
    for (int d : divisors(n)) {
        result += phi(n / d) * pow(k, d);
    }
    return result / n;
}

Referenced by main().

partition_distinct()

std::vector< std::vector< int > > gpmp::Comb::partition_distinct

(

int

n

)

Generate all distinct partitions of a positive integer n.

Parameters

n	The integer to partition

Returns

A vector of distinct partitions

Definition at line 159 of file comb.cpp.

                                                            {
    std::vector<std::vector<int>> result;
    std::vector<int> partition;
    gen_partition_distinct(n, n, partition, result);
    return result;
}

Referenced by main().

partitions()

std::vector< std::vector< int > > gpmp::Comb::partitions

(

int

n

)

Generate all partitions of a positive integer n.

Parameters

n	The integer to partition

Returns

A vector of partitions

Definition at line 91 of file comb.cpp.

                                                    {
    std::vector<std::vector<int>> result;
    std::vector<int> partition;
    generatePartitions(n, n, partition, result);
    return result;
}

Referenced by main().

permutation()

int64_t gpmp::Comb::permutation	(	int	n,
		int	r
	)

Calculate the number of permutations (nPr)

Parameters

n	The total number of items
r	The number of items to choose

Returns

The number of permutations

Definition at line 41 of file comb.cpp.

                                          {
    if (n < r)
        return 0; // Invalid input
    int64_t result = 1;
    for (int i = 0; i < r; ++i) {
        result *= (n - i);
    }
    return result;
}

Referenced by main().

permutations()

template<typename T >

std::vector<std::vector<T> > gpmp::Comb::permutations

(

const std::vector< T > &

vec

)

Generate all permutations of a vector.

Template Parameters

T	The type of elements in the vector

Parameters

vec	The vector

Returns

A vector of all permutations

Referenced by main().

phi()

int gpmp::Comb::phi

(

int

n

)

Calculate Euler's totient function (φ)

Parameters

n	The integer

Returns

The value of φ(n)

Definition at line 199 of file comb.cpp.

                       {
    int result = n;
    for (int p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) {
                n /= p;
            }
            result -= result / p;
        }
    }
    if (n > 1) {
        result -= result / n;
    }
    return result;
}

stirling_num()

int64_t gpmp::Comb::stirling_num	(	int	n,
		int	k
	)

Calculate the Stirling number of the second kind.

Parameters

n	The total number of items
k	The number of non-empty subsets

Returns

The Stirling number

Definition at line 111 of file comb.cpp.

                                           {
    if (n < k)
        return 0;
    if (n == 0 && k == 0)
        return 1;
    if (k == 0 || k == n)
        return 1;
    return k * stirling_num(n - 1, k) + stirling_num(n - 1, k - 1);
}

Referenced by main().

subfactorial()

int64_t gpmp::Comb::subfactorial

(

int

n

)

Calculate the subfactorial (!n) or derangement of n.

Parameters

n	The number

Returns

The subfactorial of n

Definition at line 131 of file comb.cpp.

                                    {
    if (n == 0)
        return 1;
    if (n == 1)
        return 0;
    return (n - 1) * (subfactorial(n - 1) + subfactorial(n - 2));
}

Referenced by main().

subsequences()

int64_t gpmp::Comb::subsequences	(	int	n,
		int	k
	)

Calculate the number of subsequences of length k from n items.

Parameters

n	The total number of items
k	The length of subsequences

Returns

The number of subsequences

Definition at line 141 of file comb.cpp.

                                           {
    if (k > n)
        return 0;
    std::vector<int64_t> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = i - 1; j >= 0; --j) {
            dp[i] += dp[j];
        }
    }
    int64_t result = 0;
    for (int i = n - k; i <= n; ++i) {
        result += dp[i];
    }
    return result;
}

Referenced by main().

---

The documentation for this class was generated from the following files:

• include/openGPMP/disct/comb.hpp
• modules/disct/comb.cpp