gridtools

Filename: gridtools.py

Authors: Pablo Winant, Daisuke Oyama

Implements cartesian products and regular cartesian grids, and provides a function that constructs a grid for a simplex as well as one that determines the index of a point in the simplex.

quantecon.gridtools.cartesian(nodes, order='C')[source]

Cartesian product of a list of arrays

Parameters:

nodes : list(array_like(ndim=1))

order : str, optional(default=’C’)

(‘C’ or ‘F’) order in which the product is enumerated

Returns:

out : ndarray(ndim=2)

each line corresponds to one point of the product space

quantecon.gridtools.mlinspace(a, b, nums, order='C')[source]

Constructs a regular cartesian grid

Parameters:

a : array_like(ndim=1)

lower bounds in each dimension

b : array_like(ndim=1)

upper bounds in each dimension

nums : array_like(ndim=1)

number of nodes along each dimension

order : str, optional(default=’C’)

(‘C’ or ‘F’) order in which the product is enumerated

Returns:

out : ndarray(ndim=2)

each line corresponds to one point of the product space

quantecon.gridtools.num_compositions(m, n)[source]

The total number of m-part compositions of n, which is equal to (n+m-1) choose (m-1).

Parameters:

m : scalar(int)

Number of parts of composition.

n : scalar(int)

Integer to decompose.

Returns:

scalar(int)

Total number of m-part compositions of n.

quantecon.gridtools.simplex_grid[source]

Construct an array consisting of the integer points in the (m-1)-dimensional simplex \(\{x \mid x_0 + \cdots + x_{m-1} = n \}\), or equivalently, the m-part compositions of n, which are listed in lexicographic order. The total number of the points (hence the length of the output array) is L = (n+m-1)!/(n!*(m-1)!) (i.e., (n+m-1) choose (m-1)).

Parameters:

m : scalar(int)

Dimension of each point. Must be a positive integer.

n : scalar(int)

Number which the coordinates of each point sum to. Must be a nonnegative integer.

Returns:

out : ndarray(int, ndim=2)

Array of shape (L, m) containing the integer points in the simplex, aligned in lexicographic order.

Notes

A grid of the (m-1)-dimensional unit simplex with n subdivisions along each dimension can be obtained by simplex_grid(m, n) / n.

References

A. Nijenhuis and H. S. Wilf, Combinatorial Algorithms, Chapter 5, Academic Press, 1978.

Examples

>>> simplex_grid(3, 4)
array([[0, 0, 4],
       [0, 1, 3],
       [0, 2, 2],
       [0, 3, 1],
       [0, 4, 0],
       [1, 0, 3],
       [1, 1, 2],
       [1, 2, 1],
       [1, 3, 0],
       [2, 0, 2],
       [2, 1, 1],
       [2, 2, 0],
       [3, 0, 1],
       [3, 1, 0],
       [4, 0, 0]])
>>> simplex_grid(3, 4) / 4
array([[ 0.  ,  0.  ,  1.  ],
       [ 0.  ,  0.25,  0.75],
       [ 0.  ,  0.5 ,  0.5 ],
       [ 0.  ,  0.75,  0.25],
       [ 0.  ,  1.  ,  0.  ],
       [ 0.25,  0.  ,  0.75],
       [ 0.25,  0.25,  0.5 ],
       [ 0.25,  0.5 ,  0.25],
       [ 0.25,  0.75,  0.  ],
       [ 0.5 ,  0.  ,  0.5 ],
       [ 0.5 ,  0.25,  0.25],
       [ 0.5 ,  0.5 ,  0.  ],
       [ 0.75,  0.  ,  0.25],
       [ 0.75,  0.25,  0.  ],
       [ 1.  ,  0.  ,  0.  ]])
quantecon.gridtools.simplex_index(x, m, n)[source]

Return the index of the point x in the lexicographic order of the integer points of the (m-1)-dimensional simplex \(\{x \mid x_0 + \cdots + x_{m-1} = n\}\).

Parameters:

x : array_like(int, ndim=1)

Integer point in the simplex, i.e., an array of m nonnegative itegers that sum to n.

m : scalar(int)

Dimension of each point. Must be a positive integer.

n : scalar(int)

Number which the coordinates of each point sum to. Must be a nonnegative integer.

Returns:

idx : scalar(int)

Index of x.