combinatorics

Useful routines for combinatorics

quantecon.util.combinatorics.k_array_rank(a)[source]

Given an array a of k distinct nonnegative integers, sorted in ascending order, return its ranking in the lexicographic ordering of the descending sequences of the elements [1].

Parameters:
andarray(int, ndim=1)

Array of length k.

Returns:
idxscalar(int)

Ranking of a.

References

quantecon.util.combinatorics.k_array_rank_jit(a)[source]

Numba jit version of k_array_rank.

Notes

An incorrect value will be returned without warning or error if overflow occurs during the computation. It is the user’s responsibility to ensure that the rank of the input array fits within the range of possible values of np.intp; a sufficient condition for it is scipy.special.comb(a[-1]+1, len(a), exact=True) <= np.iinfo(np.intp).max.

quantecon.util.combinatorics.next_k_array(a)[source]

Given an array a of k distinct nonnegative integers, sorted in ascending order, return the next k-array in the lexicographic ordering of the descending sequences of the elements [1]. a is modified in place.

Parameters:
andarray(int, ndim=1)

Array of length k.

Returns:
andarray(int, ndim=1)

View of a.

References

Examples

Enumerate all the subsets with k elements of the set {0, …, n-1}.

>>> n, k = 4, 2
>>> a = np.arange(k)
>>> while a[-1] < n:
...     print(a)
...     a = next_k_array(a)
...
[0 1]
[0 2]
[1 2]
[0 3]
[1 3]
[2 3]