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, const int b)
	Checks whether a diophantine has a solution. More...
bool	next_solution (std::vector< unsigned > &x, const std::vector< unsigned > &a, const 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, const 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,
		const 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

x	Vector to store the first solution into (resize and fill is handled by this function)
a	The constant coefficients, strictly descending (no duplicate values) and non-zero.
b	The sought inner product result

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

Checks whether a diophantine has a solution.

Parameters

a	The constant coefficients, in no particular order and without value constraints. The list may not be empty, though.
b	The 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,
		const 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

x	Filled coefficient vector of equal size as a, whose values represent a solution to the diophantine (i.e. inner_product(a, x) == b)
a	The constant coefficients, strictly descending (no duplicate values) and non-zero.
b	The sought inner product result