Generate Sorted Polynomial Features

Problem

Generate sorted polynomial features up to a given degree for a dataset. Given a 2D NumPy array of shape (n_samples, n_features) and a degree d, produce all polynomial feature combinations up to degree d, sorted in graded lexicographic order.

Solution

import numpy as np
from itertools import combinations_with_replacement

def generate_polynomial_features(X, degree):
    n_samples, n_features = X.shape
    feature_indices = range(n_features)
    output_features = []

    for d in range(degree + 1):
        for combo in combinations_with_replacement(feature_indices, d):
            feature_col = np.ones(n_samples)
            for idx in combo:
                feature_col *= X[:, idx]
            output_features.append(feature_col)

    return np.column_stack(output_features) if output_features else np.ones((n_samples, 1))

Explanation

1. For each degree from 0 to d, generate all combinations with replacement of feature indices.
2. Degree 0 gives a bias column of ones. Degree 1 gives the original features. Higher degrees give products of features.
3. Multiply the selected columns element-wise to produce each polynomial feature.
4. Stack all generated columns horizontally.

Complexity

• Time: O(n * C(n_features + d, d)) where C is the binomial coefficient
• Space: O(n * C(n_features + d, d)) for the output matrix