Berechnen Sie alle d-dimensionalen Monomalen Grad weniger als k

Question

Ich möchte alle d-dimensionalen Monomalen Grad weniger als k berechnen und sie in ein Zell-Array - Pbase - in einer geordneten Weise (ich benutze Matlab aber dieses plfblem gilt auch für andere Sprachen). k und d werden vom Benutzer zur Verfügung gestellt, aber willkürlich.

Was ich bisher getan haben, (die Array genannt degreeindex zeigen die Position von Monome einem gewissen Grad in Pbase):

n=nchoosek(d+k,k);%i know there are n over k possibilities for such monomials 
Pbase=cell(1,n); 
degreeindex=zeros(k+1,3);%showing [degree, start, end] 
x=sym('x',[d,1]); 

%the polynomials of degree 0 
Pbase{1}=1; 
degreeindex(1,1:3)=[0,1,1];%initialized for degree 0 

%degree 1 monomials 
degree=2; 
degreeindex(degree,:)=[degree-1,degreeindex(degree-1,3)+1,degreeindex(degree-1,3)+1]; 
for i=1:d 
    Pbase{degreeindex(degree,2)+i-1}=x(i); 
    degreeindex(degree,3)=degreeindex(degree,3)+1; 
end 

%degree2 monomials 
degree=3; 
degreeindex(degree,:)=[degree-1,degreeindex(degree-1,3),degreeindex(degree-1,3)+1]; 
for i=1:d 
    for j=i:d 
     Pbase{degreeindex(degree,3)-1}=x(i).*x(j); 
     degreeindex(degree,3)=degreeindex(degree,3)+1; 
    end 
end 

%degree3 monomials 
degree=4; 
degreeindex(degree,:)=[degree-1,degreeindex(degree-1,3),degreeindex(degree-1,3)+1]; 
for i1=1:d 
    for i2=i1:d 
     for i3=i2:d 
     Pbase{degreeindex(degree,3)-1}=x(i1).*x(i2)*x(i3); 
     degreeindex(degree,3)=degreeindex(degree,3)+1; 
     end 
    end 
end 
... 

Das Problem ist, dass ich das nicht einen Weg finden, zu tun für einen beliebigen Grad k. In der obigen Lösung müsste ich für jeden Grad eine neue (und tiefere) verschachtelte Schleife einfügen.

Ich weiß, dass dies wie ein triviales Problem scheint, aber ich kann es nicht verstehen. Ich schätze alle Ratschläge.

Answer 1

Sie versuchen, eine Art von Partitionierung durchzuführen, insbesondere möchten Sie alle integer partitions von k in m oder weniger Teile finden (wo Reihenfolge wichtig ist).

Mit nchoosek Sie können dies leicht achive (aus der Matlab File Exchange, here):

d = 3; % num dims 
k = 4; % degree 
x=sym('x',[d,1]); 
m = nchoosek(k+d-1,d-1); 
dividers = [zeros(m,1),nchoosek((1:(k+d-1))',d-1),ones(m,1)*(k+d)]; 
a = diff(dividers,1,2)-1; 
PBase = cell(1, size(a,1)); 
for i = 1:size(a,1) 
    PBase{i} = prod(x.' .^ a(i,:)); 
end 

Schleife über was auch immer Werte von k Sie benötigen.

Answer 2

Überprüfen Sie meine FileExchange-Einreichung für multivariate polynomische Regression. Innerhalb eines gegebenen Grades berechne ich alle Monome eines Basispolynoms mit einem beliebigen Grad. Es ist blitzschnell, aber auf Kosten von etwas Speicher.

MultiPolyRegress

Dies ist der entsprechende Abschnitt:

% Function Parameters 
NData = size(Data,1); 
NVars = size(Data,2); 
RowMultiB = '1'; 
RowMultiC = '1'; 
Lim = max(PV); 

% Initialize 
A=zeros(Lim^NVars,NVars); 

% Create Colums Corresponding to Mathematical Base 
for ii=1:NVars 
    A(:,ii)=mod(floor((1:Lim^NVars)/Lim^(ii-1)),Lim); 
end 

% Flip - Reduce - Augment 
A=fliplr(A); A=A(sum(A,2)<=Lim,:); Ab=diag(repmat(Lim,[1,NVars])); A=[A;Ab]; 

% Degree Conditionals 
for ii=1:NVars 
    A=A(A(:,ii)<=PV(ii),:); 
end 

Beachten Sie, dass es für Schleifen keine expliziten ist, die auf Leistung abhängen, nur von der Anzahl der Variablen im Polynom. Beachten Sie auch die potentiell gigantische Matrix A. Lassen Sie mich wissen, ob Sie weitere Hilfe benötigen, nachdem Sie diese angesehen haben.