asa299


asa299, a C code which generates, one at a time, the lattice points (integer coordinates) contained in a simplex, by Chasalow and Brand;

This 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:

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 MIT 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:

asa299_test

combo, a C code which enumerates combinations, partitions, subsets, index sets, and other combinatorial objects.

subset, a C code which enumerates combinations, partitions, subsets, index sets, and other combinatorial objects.

Author:

Original FORTRAN77 version by Scott Chasalow, Richard Brand; Matlab version by John Burkardt.

Reference:

  1. Scott Chasalow, Richard Brand,
    Algorithm AS 299: Generation of Simplex Lattice Points,
    Applied Statistics,
    Volume 44, Number 4, 1995, pages 534-545.
  2. 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:


Last revised on 31 May 2019.