Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Combinatorics for generating polynomial terms of degree <=k
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment