Re: Partition code

["Elie_CALI" <elie.cali@wanadoo.fr>]

Hi,

I tried some easy improvements. On my computer, your version takes 672ms,
mine 344ms.
Please check the differences, besause I didn't try to understand the
algorithm, just to change easy technical things.

{partit2(nmax)=\
cp=4;
n=nmax;
v=vector(n);
v[1]=vector(1);
v[1][1]=[1];
v[2]=vector(2);
v[2][1]=[2,0];
v[2][2]=[1,1];
for (i=3,n,v[i]=vector(cp);
vc=1;
i1=i-1;
vi1=v[i1];
for (j=1,length(vi1),
vi1j=vi1[j];
v[i][vc]=concat(vi1j,0);v[i][vc][1]++;vc++;
\\ v[i][vc]=vector(i,x,if (x<i,vi1[j][x],0));v[i][vc][1]++;vc++;
for (k=2,length(vi1j),
if (vi1j[k]<vi1j[k-1],
v[i][vc]=concat(vi1j,0);v[i][vc][k]++;vc++)));
\\ v[i][vc]=vector(i,x,if (x<i,vi1j[x],0));v[i][vc][k]++;vc++)));
v[i][vc-1]=vector(i,x,1);
v[i]=vecsort(v[i],,2);
v[i]=vector(cp,x,v[i][cp+1-x]);
for (j=1,length(v[i])-1,if (v[i][j]==v[i][j+1],v[i][j]=[0]));
v[i]=vecsort(v[i],,2);
j=1;
while (v[i][j]==[0],j++);
v[i]=vecextract(v[i],concat(concat(j,".."),cp));
vl=length(v[i]);
v[i]=vector(vl,x,v[i][vl+1-x]);
cp+=vl;
print(v[i]));
for (i=1,n,print1(","length(v[i])))
}

friendly,
Elie CALI.

----- Original Message ----- 
From: "Jon Perry" <perry@globalnet.co.uk>
To: "Pari-Users@List. Cr. Yp. To" <pari-users@list.cr.yp.to>
Sent: Thursday, February 12, 2004 3:07 PM
Subject: Partition code


> This code generates all the partitions for n. It runs out of stack space
> (4Mb) at about n=25, but only takes ~30secs at 100Mhz to n=20.
>
> Can anyone suggest any improvements?
>
> {
> cp=4;
> n=20;
> v=vector(n);
> v[1]=vector(1);
> v[1][1]=[1];
> v[2]=vector(2);
> v[2][1]=[2,0];
> v[2][2]=[1,1];
> for (i=3,n,v[i]=vector(cp);
> vc=1;
> i1=i-1;
> for (j=1,length(v[i1]),
> v[i][vc]=vector(i,x,if (x<i,v[i1][j][x],0));v[i][vc][1]++;vc++;
> for (k=2,length(v[i1][j]),
> if (v[i1][j][k]<v[i1][j][k-1],
> v[i][vc]=vector(i,x,if (x<i,v[i1][j][x],0));v[i][vc][k]++;vc++)));
> v[i][vc-1]=vector(i,x,1);
> v[i]=vecsort(v[i],,2);
> v[i]=vector(cp,x,v[i][cp+1-x]);
> for (j=1,length(v[i])-1,if (v[i][j]==v[i][j+1],v[i][j]=[0]));
> v[i]=vecsort(v[i],,2);
> j=1;
> while (v[i][j]==[0],j++);
> v[i]=vecextract(v[i],concat(concat(j,".."),cp));
> vl=length(v[i]);
> v[i]=vector(vl,x,v[i][vl+1-x]);
> cp+=vl;
> print(v[i]));
> for (i=1,n,print1(","length(v[i])))
> }
>
> I'll let you decipher the code, but a couple of clues:
>
> If the partitions of 3 are [3,0,0], [2,1,0], [1,1,1], then we generate
> [4,0,0,0],[3,1,0,0] and [3,1,0,0], [2,2,0,0], [2,1,1,0] and [2,1,1,0] and
> [1,1,1,1]. These are then sorted and sieved for repeats.
>
> See
> http://www.users.globalnet.co.uk/~perry/maths/recentstuff/recentstuff.htm
>
> for more info.
>
> Jon Perry
> perry@globalnet.co.uk
> http://www.users.globalnet.co.uk/~perry/maths/
> http://www.users.globalnet.co.uk/~perry/DIVMenu/
> BrainBench MVP for HTML and JavaScript
> http://www.brainbench.com
>
>