Molassembler  3.0.0
Molecule graph and conformer library
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Scine::Molassembler::Shapes::Diophantine Namespace Reference

Functions to help treat a particular linear diophantine equation. More...

Functions

bool has_solution (const std::vector< unsigned > &a, int b)
 Checks whether a diophantine has a solution. More...
 
bool next_solution (std::vector< unsigned > &x, const std::vector< unsigned > &a, int b)
 Finds the next solution of the diophantine equation, if it exists. More...
 
bool first_solution (std::vector< unsigned > &x, const std::vector< unsigned > &a, int b)
 Finds the first solution of the diophantine equation, if it exists. More...
 

Detailed Description

Functions to help treat a particular linear diophantine equation.

Here we want to treat a special case of the linear diophantine equation \(\sum_i a_i x_i = b\) with \(a_i > 0\) and \(x_i >= 0\).

Function Documentation

bool Scine::Molassembler::Shapes::Diophantine::first_solution ( std::vector< unsigned > &  x,
const std::vector< unsigned > &  a,
int  b 
)

Finds the first solution of the diophantine equation, if it exists.

Finds the first solution of the linear diophantine \(\sum_i a_ix_i = b\) with positive \(a_i\), non-negative \(x_i\) and positive \(b\).

Use the following pattern:

std::vector<unsigned> x;
const std::vector<unsigned> a {4, 3, 2};
const int b = 12;
if(first_solution(x, a, b)) {
do {
// Do something with x
} while(next_solution(x, a, b));
}
Warning
Solutions to diophantines, even particularly easy ones like this constrained, linear diophantine, are generally complex. The approach taken here is more or less brute-force enumeration and does not scale well for many coefficients a! See https://arxiv.org/pdf/math/0010134.pdf for a sketch on how this could be properly solved.
Parameters
xVector to store the first solution into (resize and fill is handled by this function)
aThe constant coefficients, strictly descending (no duplicate values) and non-zero.
bThe sought inner product result
bool Scine::Molassembler::Shapes::Diophantine::has_solution ( const std::vector< unsigned > &  a,
int  b 
)

Checks whether a diophantine has a solution.

Parameters
aThe constant coefficients, in no particular order and without value constraints. The list may not be empty, though.
bThe sought inner product result.
Returns
whether gcd(a_1, ..., a_n) is a divisor of b. If so, the diophantine has a solution.
bool Scine::Molassembler::Shapes::Diophantine::next_solution ( std::vector< unsigned > &  x,
const std::vector< unsigned > &  a,
int  b 
)

Finds the next solution of the diophantine equation, if it exists.

Finds the next solution of the linear diophantine \(\sum_i a_ix_i = b\) with positive \(a_i\), non-negative \(x_i\) and positive \(b\).

Use the following pattern:

std::vector<unsigned> x;
const std::vector<unsigned> a {4, 3, 2};
const int b = 12;
if(first_solution(x, a, b)) {
do {
// Do something with x
} while(next_solution(x, a, b));
}
Warning
Solutions to diophantines, even particularly easy ones like this constrained, linear diophantine, are generally complex. The approach taken here is more or less brute-force enumeration and does not scale well for many coefficients a! See https://arxiv.org/pdf/math/0010134.pdf for a sketch on how this could be properly solved.
Parameters
xFilled coefficient vector of equal size as a, whose values represent a solution to the diophantine (i.e. inner_product(a, x) == b)
aThe constant coefficients, strictly descending (no duplicate values) and non-zero.
bThe sought inner product result