nilde (version 1.1-7)

nlde: 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)

Value

p.n

total number of partitions obtained.

solutions

a matrix with each column forming a partition of n.

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.

Author

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)