ASA299
Lattice Points in N-dimensional Simplex

ASA299 is a C++ library which generates, one at a time, the lattice points (integer coordinates) contained in a simplex.

ASA299 is Applied Statistics Algorithm 299.

The simplex is defined by N-dimensional points X such that:

0 <= X(1:N)

and

sum ( X(1:N) ) <= T

where T is an integer.

Lattice points are points X which satisfy the simplex conditions and for which all the components are integers.

This routine generates all the lattice points in a given simplex, one at a time, in a reverse lexicographic order.

The output for N = 3, T = 4 would be:

        1    4  0  0
        2    3  1  0
        3    3  0  1
        4    2  2  0
        5    2  1  1
        6    2  0  2
        7    1  3  0
        8    1  2  1
        9    1  1  2
       10    1  0  3
       11    0  4  0
       12    0  3  1
       13    0  2  2
       14    0  1  3
       15    0  0  4

Usage:

call simplex_lattice_point_next ( n, t, more, x )

To use the routine, initialize by setting the spatial dimension N and the simplex size parameter T to appropriate values, and set MORE to FALSE. The initial value of X is not important.

Call the routine. On return, X will contain the first lattice point in the simplex. If MORE is TRUE, then the routine may be called again to get the next point. In fact, as long as the output value of MORE is TRUE, there is at least one more lattice point that can be found by making another call. When MORE is returned as FALSE, then there are no more lattice points; the value of X returned at that time is the "last" such point.

During the computation of a sequence of lattice points, the user should not change the values of N, T, MORE or X.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

ASA299 is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

COMBO, a FORTRAN90 library which enumerates combinations, partitions, subsets, index sets, and other combinatorial objects.

SUBSET, a FORTRAN90 library which enumerates combinations, partitions, subsets, index sets, and other combinatorial objects.

Reference:

Scott Chasalow, Richard Brand,
Algorithm AS 299: Generation of Simplex Lattice Points,
Applied Statistics,
Volume 44, Number 4, 1995, pages 534-545.
Albert Nijenhuis, Herbert Wilf,
Combinatorial Algorithms for Computers and Calculators,
Second Edition,
Academic Press, 1978,
ISBN: 0-12-519260-6,
LC: QA164.N54.

Source Code:

asa299.cpp, the source code.
asa299.hpp, the source code.

Examples and Tests:

asa299_test.cpp, a sample calling program.
asa299_test.txt, the output ffile.

List of Routines:

SIMPLEX_LATTICE_POINT_NEXT generates lattice points in a simplex.
TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.

Last revised on 10 January 2007.

ASA299 Lattice Points in N-dimensional Simplex