Partitions Lookup

GeneratePartitionsLookupTable.cpp

// CPP program to generate all unique
// partitions of an integer
//https://www.timvanerven.nl/assets/publications/2010/PhDthesis-TimvanErven.pdf
//https://luna.informatik.uni-mainz.de/mod2-21/slides/S06-Information.pdf
//Bayesian updates the model given past data. i.e the probabilities  change whenever new information is given
//I'm a frequentist. Honestly, I don't even think probabilites exist. Probabilities are like astrology signs - super mainstream but 
//Meme probability to day trade is similar to astrology girl angry because mercury is in retrograde

#include<iostream>
using namespace std;

// A utility function to print an array p[] of size 'n'

void MultinomialCoefficient(int top, int length, int bottom[], long *result)
{
    double topValue = 1;
    double bottomValue = 1;
    for(int i = 0; i < top; i++)
    {
            topValue *= (double)(i+1);
    }
    
    for(int i = 0; i < length; i++)
    {
        bottomValue = 1;
        for(int j = 0; j < bottom[i]; j++)
        {
            bottomValue *= (double)(j+1);
        }
        topValue /= bottomValue;
    }
    *result = topValue;
}

void PermutationCount(int partitionLength, int partition[], long *result)
{
        int uniqueDigitCount = 0;
        int runLength[partitionLength];for(int i = 0; i < partitionLength; i++){runLength[i] = 1;}
        for(int i = 0; i < partitionLength; i++)
        {
            while(partition[i] == partition[i+1] && i+1 < partitionLength)
            {
                runLength[uniqueDigitCount] += 1;
                i+=1;
            }
           uniqueDigitCount += 1;
        }
        
        for(int i = 0; i < uniqueDigitCount; i++)
        {
            //printf("(%d)",runLength[i]);
        }
        MultinomialCoefficient(partitionLength, uniqueDigitCount,runLength,result);
}
void printArray(int p[], int n)
{
    long result = 0;
    long permutations = 0;
    MultinomialCoefficient(16, n,p, &result);
    PermutationCount(n, p, &permutations);
    printf("{%3ld,%3ld, %3d, ",result, permutations, n);
	for (int i = 0; i < 15; i++)
	{
	    if(i < n)
	    {
	        printf("%3d,",p[i]);
	    }
	    else
	    {
	        printf("%3d,",0);
	    }
	}
	
	printf("%3d},\n",0);
}

void printAllUniqueParts(int n)
{
	int p[n]; // An array to store a partition
	int k = 0; // Index of last element in a partition
	p[k] = n; // Initialize first partition as number itself

	// This loop first prints current partition then generates next
	// partition. The loop stops when the current partition has all 1s
	while (true)
	{
		// print current partition
		printArray(p, k+1);

		// Generate next partition

		// Find the rightmost non-one value in p[]. Also, update the
		// rem_val so that we know how much value can be accommodated
		int rem_val = 0;
		while (k >= 0 && p[k] == 1)
		{
			rem_val += p[k];
			k--;
		}

		// if k < 0, all the values are 1 so there are no more partitions
		if (k < 0) return;

		// Decrease the p[k] found above and adjust the rem_val
		p[k]--;
		rem_val++;


		// If rem_val is more, then the sorted order is violated. Divide
		// rem_val in different values of size p[k] and copy these values at
		// different positions after p[k]
		while (rem_val > p[k])
		{
			p[k+1] = p[k];
			rem_val = rem_val - p[k];
			k++;
		}

		// Copy rem_val to next position and increment position
		p[k+1] = rem_val;
		k++;
	}
}

// Driver program to test above functions
int main()
{
	printf("#define LOOKUP_HEIGHT 231\n#define LOOKUP_WIDTH 19\nlong LOOKUP_TABLE_16[LOOKUP_HEIGHT][LOOKUP_WIDTH] =\n{\n");
	printAllUniqueParts(16);
    printf("};\n");
	return 0;
}

Generation Partitions of a specific length and rank lexiicographically

#include <stdio.h>

int p(int n, int k) {
    if (n == 0 && k == 0) {
        return 1;
    }
    if (k == 1 || n == k) {
        return 1;
    }
    if (k > n) {
        return 0;
    }
    return p(n-1, k-1) + p(n-k, k);
}

int num_partitions(int n, int k, int p) {
    if (n < 0 || k < 0 || p <= 0) {
        return 0;
    }
    if (n == 0 && k == 0) {
        return 1;
    }
    return num_partitions(n - p, k - 1, p)
           + num_partitions(n, k, p - 1);
}

int partition_rank(int *arr, int arr_length) {
    int n = 0;
    int k = 0;
    for (int i = 0; i < arr_length; i++) {
        n += arr[i];
        k++;
    }
    int _n = n;
    int _k = k;
    int r = 0;
    for (int i = 0; i < arr_length; i++) {
        r += num_partitions(n, k, arr[i]-1);
        n -= arr[i];
        k--;
    }
    return p(_n, _k) - r - 1;
}

int main() {
    int partitions[8][3] = {{8, 1, 1}, {7, 2, 1}, {6, 3, 1}, {6, 2, 2}, {5, 4, 1}, {5, 3, 2}, {4, 4, 2}, {4, 3, 3}};
    for (int i = 0; i < 8; i++) {
        int rank = partition_rank(partitions[i], 3);
        printf("(%d, %d, %d) - Rank: %d\n", partitions[i][0], partitions[i][1], partitions[i][2], rank);
    }
    return 0;
}