Sorted polynomial features

Background

Polynomial features let a linear model fit nonlinear relationships: by adding products and powers of the original features (e.g. $x_1^2, x_1 x_2$), a linear regression in the expanded space becomes a polynomial in the original space. Including the constant term (degree 0) gives the model its bias. This is a classic, cheap way to increase model capacity.

Problem statement

Implement polynomial_features(X, degree) that expands each row of X into all monomials up to degree (including the constant term), then returns each row sorted ascending.

For degrees $d = 0,1,\dots,\text{degree}$, take every combinations_with_replacement of feature indices of size $d$; the term is the product of those features (degree 0 → the constant 1).

Input

• X — np.ndarray (n_samples, n_features).
• degree — int, the maximum total degree.

Output

An np.ndarray (n_samples, n_terms): the polynomial terms of each row, each row sorted in ascending order.

Examples

Example 1

Input:  X = [[2, 3], [3, 4], [5, 6]], degree = 2
Output: [[ 1,  2,  3,  4,  6,  9],
         [ 1,  3,  4,  9, 12, 16],
         [ 1,  5,  6, 25, 30, 36]]

Explanation: for row [2, 3] the terms are 1, 2, 3, 2*2=4, 2*3=6, 3*3=9 → sorted [1, 2, 3, 4, 6, 9].

Constraints

• Include the degree-0 constant term (value 1) for every sample.
• Generate terms with combinations_with_replacement over feature indices for each degree.
• Sort each row ascending before returning.

Notes

• The number of terms for n features up to degree d is $\binom{n+d}{d}$ — it grows fast, so high-degree expansions can explode the feature count.
• Sorting per row (this variant's twist) discards which column is which monomial; standard PolynomialFeatures keeps a fixed term order instead.