Partition code

["Jon Perry" <perry@globalnet.co.uk>]

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