Enumerate Weak Integer Compositions

WeakComposition.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 PrintArray(int length, int *array)
{
	for(int i = 0; i < length; i++)
	{
		printf("%3d, ", array[i]);	
	}
	printf("\n");
}

void EnumerateWeakCompositions(int n, int k)
{
	//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
		printf("%3d : ", currentSetIndex);
		PrintArray(k, currentComposition);
		//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;}
	}
}

int main()
{
	int n = 8;
	int k = 3;
	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);
}