Combinatorics for generating polynomial terms of degree <=k

polyMultiFeatures.m

function [ as_ ] = polyMultiFeatures( items, k )
    as = [];
    function recurse(a, i)
        % we should optimize and early stop a with length>k 
        if i>size(items,2)
            if size(a,2)<=k
                as{end+1} = a;
            end
            return;
        end
        a1 = a;
        
        % recurse all possibilities
        recurse(a1, i+1); % don't use item i
        for j=1:k
            a2 = [a repmat(items(:,i), 1, j)]; % use item i, j times
            recurse(a2, i+1);
        end
    end
    recurse([], 1);
    % remove first one which is empty
    as(1) = [];
    % now reduce all items by multiplication
    as_ = zeros(size(items,1),length(as));
    for j=1:length(as)
        as_(:,j) = prod(as{j},2);
    end
end
 
% let's test
X = [1:3; 2:4]
n = size(X,2);
k = 3;
A = polyMultiFeatures(X, k)
 
%let's check we have the right length
combinationWithRepetitions = @(n,k) factorial(n+k-1)./(factorial(n-1)*factorial(k));
length(A) == sum(combinationWithRepetitions(n,1:k))