nlde: Enumeration of all existing nonnegative integer solutions of...

In nilde: Nonnegative Integer Solutions of Linear Diophantine Equations with Applications

Enumeration of all existing nonnegative integer solutions of a linear Diophantine equation

Description

This function enumerates nonnegative integer solutions of a linear Diophantine equation (NLDE):

a_1s_1 +a_2s_2 +...+ a_ls_l =n,

where a_1 <= a_2 <= ... <= a_l, a_i > 0, n > 0, s_i >= 0, i=1,2,...,l, and all variables involved are integers.

The algorithm is based on a generating function of Hardy and Littlewood used by Voinov and Nikulin (1997).

Usage

 nlde(a, n, M=NULL, at.most=TRUE, option=0)

Arguments

a	An l-vector of positive integers (coefficients of the left-hand-side of NLDE) with l>= 2.
n	A positive integer which is to be partitioned.
M	A positive integer, the number of parts of n, M <= n.
at.most	If TRUE partitioning of n into at most M parts, if FALSE partitioning on exactly M parts.
option	When set to 1 (or any positive number) finds only 0-1 solutions of the linear Diophantine equation. When set to 2 (or any positive number > 1) finds 0-1 solutions of the linear Diophantine inequality.

Value

p.n	total number of partitions obtained.
solutions	a matrix with each column forming a partition of n.

Author(s)

Vassilly Voinov, Natalya Pya Arnqvist, Yevgeniy Voinov

References

Voinov, V. and Nikulin, M. (1997) On a subset sum algorithm and its probabilistic and other applications. In: Advances in combinatorial methods and applications to probability and statistics, Ed. N. Balakrishnan, Birkhäuser, Boston, 153-163.

Hardy, G.H. and Littlewood, J.E. (1966) Collected Papers of G.H. Hardy, Including Joint Papers with J.E. Littlewood and Others. Clarendon Press, Oxford.

See Also

nilde-package, get.partitions, get.subsetsum, get.knapsack

Examples

## some examples...
## example 1...
nlde(a=c(3,2,5,16),n=18,at.most=TRUE)
b1 <- nlde(a=c(3,2,5,16),n=18,M=6,at.most=FALSE)
b1
## checking M, the number of parts that n=18 has been partitioned into...
colSums(b1$solutions)
## checking the value of n...
colSums(b1$solutions*c(3,2,5,16))

## example 2:  solving 0-1 nlde ...
b2 <- nlde(a=c(3,2,5,16),n=18,M=6,option=1)
b2
colSums(b2$solutions*c(3,2,5,16))

## example 3...
b3 <- nlde(c(15,21),261)
b3 
## checking M, the number of parts that n has been partitioned into...
colSums(b3$solutions)
## checking the value of n...
colSums(b3$solutions*c(15,21))

## example 4... 
nlde(c(5,6),19) ## no solutions

## example 5: solving 0-1 inequality...
b4 <- nlde(a=c(70,60,50,33,33,33,11,7,3),n=100,at.most=TRUE,option=2)

nilde documentation built on Aug. 16, 2022, 5:05 p.m.