Safe Haskell | Safe-Infered |
---|
Homogeneous Linear Diaphantine Equation solver.
The solver uses the algorithm of Contejean and Devie as specified by David Papp and Bela Vizari in "Effective Solutions of Linear Diophantine Equation Systems with an Application to Chemistry", Rutcor Research Report RRR 28-2004, September, 2004, http://rutcor.rutgers.edu/pub/rrr/reports2004/28_2004.ps, after modification so as to ensure every basis vector is considered.
The algorithm for systems of homogeneous linear Diophantine equations follows. Let e[k] be the kth basis vector for 1 <= k <= n. To find the minimal, non-negative solutions M to the system of equations sum(i=1,n,a[i]*v[i]) = 0, the algorithm of Contejean and Devie is:
- [init] A := {e[k] | 1 <= k <= n}; M := {}
- [new minimal results] M := M + {a in A | a is a solution}
- [unnecessary branches] A := {a in A | all m in M : some 1 <= k <= n : m[k] < a[k]}
- [test] If A = {}, stop
- [breadth-first search] A := {a + e[k] | a in A, 1 <= k <= n, <sum(i=1,n,a[i]*v[i]),v[k]> < 0}; go to step 2
- homLinDiaphEq :: [Int] -> [[Int]]
Documentation
homLinDiaphEq :: [Int] -> [[Int]]Source
The homLinDiaphEq
function takes a list of integers that
specifies a homogeneous linear Diophantine equation, and returns
the equation's minimal, non-negative solutions.