EnumerateWeakComposition.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MAX_K 100
unsigned long long BinomialCoefficient(int n, int k)
{
	if(k > n - k){k = n - k;}
	unsigned long long result = 1;
	for(int i = 0; i < k; ++i) 
	{
		result *= (n - i);
		result /= (i + 1);
	}
	return result;
}

void CompareArray(int length, int *array0, int *array1)
{
	for(int i = 0; i < length; i++)
	{
		assert(array0[i] == array1[i]);
	}
}

void PrintArray(int length, int *array)
{
	for(int i = 0; i < length; i++)
	{
		printf("%2d,", array[i]);	
	}
	printf("\n");
}

int FindArraySum(int length, int *array)
{
	int sum = 0;
	for(int i = 0; i < length; i++)
	{
		sum += array[i];
	}
	return sum;
}

void EnumerateWeakCompositions(int n, int k, int index)
{
	//MAX_K is the total number of compositions
	assert(k < MAX_K);
	int currentComposition[MAX_K] = {0};
	//Set the first composition
	currentComposition[k-1] = n;
	int currentSetIndex = 0;
	while(1)
	{
		//Print Current Composition
		if(index == -1)
		{
			printf("%3d : ", currentSetIndex);
			PrintArray(k, currentComposition);
		}
		else
		{
			if(currentSetIndex == index)
			{
				printf("%3d : ", currentSetIndex);
				PrintArray(k, currentComposition);
				break;
			}
		}

		
		//Generate next Composition
		int i = 0;
		for(i = k - 2; i >= 0; i--)
		{
			if(currentComposition[i] < n)
			{
				int sum = 0;
				for(int j = 0; j <= i; j++){sum += currentComposition[j];}
				if(sum < n)
				{
					currentComposition[i] += 1;
					int remainder = n;
					for(int j = 0; j <= i; j++){remainder -= currentComposition[j];}
					for(int j = i + 1; j < k -1; j++){currentComposition[j] = 0;}				
					currentComposition[k-1] = remainder;
					break;
				}	
			}
		}
		//Increase currentSetIndex by 1
		currentSetIndex += 1;
		//Exit the while loop
		if(i < 0){break;}
	}
}

void GenerateRandomComposition(int n, int k, int randomTime, int *array)
{
	array[0] = n;
	for(int i = 0; i < randomTime; i++)
	{
		int a = rand() % k;
		int b = rand() % k;
		if(array[a] > 0 && array[b] < n)
		{
			array[a] -= 1;
			array[b] += 1;	
		}
	}
	//Ensure sum matches n
	int sum = FindArraySum(k, array);
	assert(sum == n);
}

//First trial
int FindWeakCompositionIndex0(int n, int k, int *array)
{
	//Ensure sum matches n
	int sum = FindArraySum(k, array);
	assert(sum == n);
	int index = -1;
	
	unsigned long long currentSum = 0;
	unsigned long long low = 0;
	unsigned long long high = BinomialCoefficient(n + k - 1, k - 1);
	int highestValue = n;
	for(int i = 0; i < k; i++)
	{
		int currentValue = array[i];
		currentSum = 0;
		printf("%lld %d (%d) %lld\n", low, currentValue, highestValue, high);
		if(i == 0)
		{
			low = 0;
			high = 0;  
			for(int j = 0; j <= currentValue && j <= highestValue; j++)
			{
				unsigned long long binomialCoefficient = BinomialCoefficient(highestValue + k-2 - j, k - 2);	
				printf("\t|%d %d %lld\n", n + k-2 - j, k - 2, binomialCoefficient);
				currentSum += binomialCoefficient;
				low = high;
				high += binomialCoefficient;
			}
		}
		else
		{
			high = low;
			for(int j = 0; j <= currentValue; j++)
			{
				unsigned long long binomialCoefficient = BinomialCoefficient(highestValue + k-2 -i - j, k - 2-i);	
				printf("\t|%d %d %lld\n", n + k-2 - j, k - 2, binomialCoefficient);
				if(j > 0){low = high;}
				high += binomialCoefficient;
					
			}
		}
		highestValue -= currentValue;
	}
	
	//Ensure it was found
	index = 1;
	assert(index > 0);
	return index;
}

//Second Trial
int FindWeakCompositionIndex(int n, int k, int *array)
{
	//Ensure sum matches n
	int sum = FindArraySum(k, array);
	assert(sum == n);
	int highestValue = n;
	int currentValue = 0;
	
	unsigned long long low = 0;
	unsigned long long high = 0;
	for(int i = 0; i < k; i++)
	{
		currentValue = array[i];
		//printf("%lld %d (%d) %lld\n", low, currentValue, highestValue, high);
		if(high - low == 1){break;}
		high = low;
		for(int j = 0; j <= currentValue; j++)
		{
			unsigned long long binomialCoefficient = BinomialCoefficient(highestValue + k-2 - i - j, k - 2- i);
			low = high;
			high += binomialCoefficient;		
		}
		highestValue -= currentValue;
	}
	assert(high-low == 1);
	EnumerateWeakCompositions(n,k, low);
	return low;
}

void IndexToWeakComposition(int index, int n, int k, int *array)
{
	assert(index > -1);
	unsigned long long low = 0;
	int highestValue = n;
	int currentValue = 0;
	for(int i = 0; i < k; i++)
	{
		for(int j = 0; j <= highestValue; j++)
		{
			unsigned long long binomialCoefficient = BinomialCoefficient(highestValue + k-2 - i - j, k - 2- i);
			if(low + binomialCoefficient > index)
			{
				currentValue = j;
				array[i] = j;
				break;
			}
			low += binomialCoefficient;
		}
		highestValue -= currentValue;
	}
	array[k-1] = highestValue;
}

int main()
{
	srand(45346);
	int n = 24;
	int k = 7;
	int randomTime = 179203;
	unsigned long long totalCompositions = BinomialCoefficient(n + k - 1, k - 1);
	printf("Weak compositions of %d into %d parts (total = %llu):\n", n, k, totalCompositions);
	//EnumerateWeakCompositions(n,k, -1);
	
	int *array0 = calloc(k, sizeof(int));
	int *array1 = calloc(k, sizeof(int));
	GenerateRandomComposition(n, k, randomTime, array0);
	PrintArray(k, array0);
	//int index0 = FindWeakCompositionIndex0(n, k, array0);
	int index = FindWeakCompositionIndex(n, k, array0);
	IndexToWeakComposition(index, n, k, array1);
	CompareArray(k, array0, array1);
	free(array0);
	free(array1);
}