Back to July Calendar

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 <iostream>
//#include <vector>
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: