Previous Entry Next Entry→

September 27, 2005

I've perhaps made a mistake by trying to improve the algorithm so that I'm keeping track of to simultaneous arrays: R[] keeps track of all the d distinct numbers in the partition, and M[] notes their respective multiplicity in the partition.  Thus for a partition of N, we will always have that sum(R[i]*M[i], i=0..N-1) = N

It is not a trivial exercise (at least for me) to develop an algorithm incorporating this improvement.  Here;s the pseudocode in Nijenhuis/Wilf for NEXPAR:

1. [First entryr1nm1 1; d 1;  Exit

2. [Later entries]  (Set σ equal to the sum of all parts of size one, plus the part preceding them.)
If
rd = 1, set σ ←  md + 1, d d1; otherwise, σ 1.

3. [Remove one part of size rd ]   f rd – 1;  if md = 1, to (D); md md 1; d d + 1.

4. [Add new parts of size f]   rd f;  md floor(σ/f ) + 1.

5. [Add positive remainder] s  σ (mod f);  If s = 0. to (F); otherwise d d + 1; rd smd 1.

6. [Exit]  If md = n, final exit; Exit.

Note: the only way to skip skipping onto D in C is if rd 1 (so σ=1) and md 1.

Here's c++ code I wrote to implement this algorithm.  It also counts the partitions as it goes along, so it's a new way of doing that too!

 ``````#include //#include using namespace std; //void NexPar(int []); void printPar(int [], int []); int main() { cout << "*************************************\n" << "* List all the partitions of *\n" << "* a given integer in antilex order. *\n" << "*************************************\n"; cout << "********************************************\n" << "* pseudocode: *\n" << "* if R[d] > 1 then *\n" << "* --R[d]; ++d; R[d] = 1; *\n" << "* else *\n" << "* f = R[d]-1; regroup = M[d]+R[d-1] *\n" << "* M[d-1] = regroup/f; s = regroup%f *\n" << "* if s != 0 then *\n" << "* ++d; R[d] = s; M[d] = 1; *\n" << "********************************************\n"; const int arraySize = 20; int R[arraySize]={0}, M[arraySize]={0}; // d is the number of distinct parts in the output partition // R contains the distinct parts -> R[d] is the last entry // M contains the multiplicity of the parts int n=1,d,f,sum,rem,count=0; while(n>0) { count = 1; cout << "\nEnter the integer whose partitions are to be listed: "; cin >> n; //cout << "\n " << n; // initialize parameters for(int i = 1; i < arraySize; ++i) { R[i] = 0; M[i] = 0; } R[0]=n; M[0]=1; d=0; cout << n; do { // The exit condition is a multiplicity of n 1's. // if there is not a string of one or more 1's at the end ++count; if (R[d]>1) sum = 1; else { sum = M[d]+1; R[d]=0; --d; } // Remove one part of size R[d] f = R[d] - 1; // If there is more than 1 item of smallest size, // decrease this number and increase the number of distinct items // This doesn't seem to happen very often? if(M[d]!=1) { --M[d]; ++d; } // add new parts of size f R[d] = f; M[d] = sum/f+1; // add positive remainder rem = sum%f; if (rem != 0) { ++d; R[d]=rem; M[d]=1; }//end if printPar(R,M); } while(M[d]!=n); // end while cout << "\nThere are " << count << " partitions of " << n; }//end while } // end main void printPar(int R[20], int M[20]) { int i = 0; cout << endl; while (R[i]!=0) { for(int j=0; j < M[i]; ++j) cout << R[i] << " "; ++i; } }``````

Here's a sampling of output using n = 17, to honor the fading memory of Matthews...whatever happened to him?

 Enter the integer whose partitions are to be listed: 17 17 16 1 15 2 15 1 1 14 3 14 2 1 14 1 1 1 13 4 13 3 1 13 2 2 13 2 1 1 13 1 1 1 1 12 5 12 4 1 12 3 2 12 3 1 1 12 2 2 1 12 2 1 1 1 12 1 1 1 1 1 11 6 11 5 1 11 4 2 11 4 1 1 11 3 3 11 3 2 1 11 3 1 1 1 11 2 2 2 11 2 2 1 1 11 2 1 1 1 1 11 1 1 1 1 1 1 10 7 10 6 1 10 5 2 10 5 1 1 10 4 3 10 4 2 1 10 4 1 1 1 10 3 3 1 10 3 2 2 10 3 2 1 1 10 3 1 1 1 1 10 2 2 2 1 10 2 2 1 1 1 10 2 1 1 1 1 1 10 1 1 1 1 1 1 1 9 8 9 7 1 9 6 2 9 6 1 1 9 5 3 9 5 2 1 9 5 1 1 1 9 4 4 9 4 3 1 9 4 2 2 9 4 2 1 1 9 4 1 1 1 1 9 3 3 2 9 3 3 1 1 9 3 2 2 1 9 3 2 1 1 1 9 3 1 1 1 1 1 9 2 2 2 2 9 2 2 2 1 1 9 2 2 1 1 1 1 9 2 1 1 1 1 1 1 9 1 1 1 1 1 1 1 1 8 8 1 8 7 2 8 7 1 1 8 6 3 8 6 2 1 8 6 1 1 1 8 5 4 8 5 3 1 8 5 2 2 8 5 2 1 1 8 5 1 1 1 1 8 4 4 1 8 4 3 2 8 4 3 1 1 8 4 2 2 1 8 4 2 1 1 1 8 4 1 1 1 1 1 8 3 3 3 8 3 3 2 1 8 3 3 1 1 1 8 3 2 2 2 8 3 2 2 1 1 8 3 2 1 1 1 1 8 3 1 1 1 1 1 1 8 2 2 2 2 1 8 2 2 2 1 1 1 8 2 2 1 1 1 1 1 8 2 1 1 1 1 1 1 1 8 1 1 1 1 1 1 1 1 1 7 7 3 7 7 2 1 7 7 1 1 1 7 6 4 7 6 3 1 7 6 2 2 7 6 2 1 1 7 6 1 1 1 1 7 5 5 7 5 4 1 7 5 3 2 7 5 3 1 1 7 5 2 2 1 7 5 2 1 1 1 7 5 1 1 1 1 1 7 4 4 2 7 4 4 1 1 7 4 3 3 7 4 3 2 1 7 4 3 1 1 1 7 4 2 2 2 7 4 2 2 1 1 7 4 2 1 1 1 1 7 4 1 1 1 1 1 1 7 3 3 3 1 7 3 3 2 2 7 3 3 2 1 1 7 3 3 1 1 1 1 7 3 2 2 2 1 7 3 2 2 1 1 1 7 3 2 1 1 1 1 1 7 3 1 1 1 1 1 1 1 7 2 2 2 2 2 7 2 2 2 2 1 1 7 2 2 2 1 1 1 1 7 2 2 1 1 1 1 1 1 7 2 1 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1 1 1 1 6 6 5 6 6 4 1 6 6 3 2 6 6 3 1 1 6 6 2 2 1 6 6 2 1 1 1 6 6 1 1 1 1 1 6 5 5 1 6 5 4 2 6 5 4 1 1 6 5 3 3 6 5 3 2 1 6 5 3 1 1 1 6 5 2 2 2 6 5 2 2 1 1 6 5 2 1 1 1 1 6 5 1 1 1 1 1 1 6 4 4 3 6 4 4 2 1 6 4 4 1 1 1 6 4 3 3 1 6 4 3 2 2 6 4 3 2 1 1 6 4 3 1 1 1 1 6 4 2 2 2 1 6 4 2 2 1 1 1 6 4 2 1 1 1 1 1 6 4 1 1 1 1 1 1 1 6 3 3 3 2 6 3 3 3 1 1 6 3 3 2 2 1 6 3 3 2 1 1 1 6 3 3 1 1 1 1 1 6 3 2 2 2 2 6 3 2 2 2 1 1 6 3 2 2 1 1 1 1 6 3 2 1 1 1 1 1 1 6 3 1 1 1 1 1 1 1 1 6 2 2 2 2 2 1 6 2 2 2 2 1 1 1 6 2 2 2 1 1 1 1 1 6 2 2 1 1 1 1 1 1 1 6 2 1 1 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1 1 1 1 5 5 5 2 5 5 5 1 1 5 5 4 3 5 5 4 2 1 5 5 4 1 1 1 5 5 3 3 1 5 5 3 2 2 5 5 3 2 1 1 5 5 3 1 1 1 1 5 5 2 2 2 1 5 5 2 2 1 1 1 5 5 2 1 1 1 1 1 5 5 1 1 1 1 1 1 1 5 4 4 4 5 4 4 3 1 5 4 4 2 2 5 4 4 2 1 1 5 4 4 1 1 1 1 5 4 3 3 2 5 4 3 3 1 1 5 4 3 2 2 1 5 4 3 2 1 1 1 5 4 3 1 1 1 1 1 5 4 2 2 2 2 5 4 2 2 2 1 1 5 4 2 2 1 1 1 1 5 4 2 1 1 1 1 1 1 5 4 1 1 1 1 1 1 1 1 5 3 3 3 3 5 3 3 3 2 1 5 3 3 3 1 1 1 5 3 3 2 2 2 5 3 3 2 2 1 1 5 3 3 2 1 1 1 1 5 3 3 1 1 1 1 1 1 5 3 2 2 2 2 1 5 3 2 2 2 1 1 1 5 3 2 2 1 1 1 1 1 5 3 2 1 1 1 1 1 1 1 5 3 1 1 1 1 1 1 1 1 1 5 2 2 2 2 2 2 5 2 2 2 2 2 1 1 5 2 2 2 2 1 1 1 1 5 2 2 2 1 1 1 1 1 1 5 2 2 1 1 1 1 1 1 1 1 5 2 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 1 1 4 4 4 4 1 4 4 4 3 2 4 4 4 3 1 1 4 4 4 2 2 1 4 4 4 2 1 1 1 4 4 4 1 1 1 1 1 4 4 3 3 3 4 4 3 3 2 1 4 4 3 3 1 1 1 4 4 3 2 2 2 4 4 3 2 2 1 1 4 4 3 2 1 1 1 1 4 4 3 1 1 1 1 1 1 4 4 2 2 2 2 1 4 4 2 2 2 1 1 1 4 4 2 2 1 1 1 1 1 4 4 2 1 1 1 1 1 1 1 4 4 1 1 1 1 1 1 1 1 1 4 3 3 3 3 1 4 3 3 3 2 2 4 3 3 3 2 1 1 4 3 3 3 1 1 1 1 4 3 3 2 2 2 1 4 3 3 2 2 1 1 1 4 3 3 2 1 1 1 1 1 4 3 3 1 1 1 1 1 1 1 4 3 2 2 2 2 2 4 3 2 2 2 2 1 1 4 3 2 2 2 1 1 1 1 4 3 2 2 1 1 1 1 1 1 4 3 2 1 1 1 1 1 1 1 1 4 3 1 1 1 1 1 1 1 1 1 1 4 2 2 2 2 2 2 1 4 2 2 2 2 2 1 1 1 4 2 2 2 2 1 1 1 1 1 4 2 2 2 1 1 1 1 1 1 1 4 2 2 1 1 1 1 1 1 1 1 1 4 2 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 2 3 3 3 3 3 1 1 3 3 3 3 2 2 1 3 3 3 3 2 1 1 1 3 3 3 3 1 1 1 1 1 3 3 3 2 2 2 2 3 3 3 2 2 2 1 1 3 3 3 2 2 1 1 1 1 3 3 3 2 1 1 1 1 1 1 3 3 3 1 1 1 1 1 1 1 1 3 3 2 2 2 2 2 1 3 3 2 2 2 2 1 1 1 3 3 2 2 2 1 1 1 1 1 3 3 2 2 1 1 1 1 1 1 1 3 3 2 1 1 1 1 1 1 1 1 1 3 3 1 1 1 1 1 1 1 1 1 1 1 3 2 2 2 2 2 2 2 3 2 2 2 2 2 2 1 1 3 2 2 2 2 2 1 1 1 1 3 2 2 2 2 1 1 1 1 1 1 3 2 2 2 1 1 1 1 1 1 1 1 3 2 2 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 2 2 1 1 1 1 1 2 2 2 2 2 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 There are 297 partitions of 17. Enter the integer whose partitions are to be listed: