Skip to content

Instantly share code, notes, and snippets.

@MurageKibicho
Created July 12, 2025 06:59
Show Gist options
  • Save MurageKibicho/9618d620ef7e4d71d3401b58445e59c8 to your computer and use it in GitHub Desktop.
Save MurageKibicho/9618d620ef7e4d71d3401b58445e59c8 to your computer and use it in GitHub Desktop.
Using LibGMP to enumerate integer compositions
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdint.h>
#include <gmp.h>
#include <assert.h>
#define STB_DS_IMPLEMENTATION
#include "stb_ds.h"
//clear && gcc Nichols.c -lm -lgmp -o m.o && ./m.o
typedef struct dictionary_entry_struct *DictionaryEntry;
typedef DictionaryEntry* Dictionary;
struct dictionary_entry_struct
{
int number;
int frequency;
};
DictionaryEntry CreateDictionaryEntry(int number)
{
DictionaryEntry entry = malloc(sizeof(struct dictionary_entry_struct));
entry->number = number;
entry->frequency = 1;
return entry;
}
void DestroyDictionaryEntry(DictionaryEntry entry)
{
if(entry)
{
free(entry);
}
}
Dictionary CreateDictionary(int length, int *array)
{
Dictionary dictionary = NULL;
for(int i = 0; i < length; i++)
{
int found = 0;
for(size_t j = 0; j < arrlen(dictionary); j++)
{
if(dictionary[j]->number == array[i])
{
found = 1;
dictionary[j]->frequency += 1;
break;
}
}
if(found == 0)
{
DictionaryEntry entry = CreateDictionaryEntry(array[i]);
arrput(dictionary, entry);
}
}
return dictionary;
}
void PrintDictionary(Dictionary dictionary)
{
printf("Entries : %ld\n",arrlen(dictionary));
for(size_t i = 0; i < arrlen(dictionary); i++)
{
printf("%d %d\n",dictionary[i]->number,dictionary[i]->frequency);
}
}
void DeleteDictionary(Dictionary dictionary)
{
if(dictionary)
{
for(size_t i = 0; i < arrlen(dictionary); i++)
{
DestroyDictionaryEntry(dictionary[i]);
}
arrfree(dictionary);
}
}
void TestDictionary()
{
srand(234562);
int length = 10;
int modulo = 100;
int *array = calloc(length ,sizeof(int));
for(int i = 0; i < length; i++)
{
array[i] = rand() % modulo;
printf("%d, ", array[i]);
}
printf("\n");
Dictionary dictionary = CreateDictionary(length, array);
PrintDictionary(dictionary);
DeleteDictionary(dictionary);
free(array);
}
void PrintIntArray(int length, int *array){for(int i = 0; i < length; i++){printf("%2d,", array[i]);}printf("\n");}
int *RandomPositiveArray(int length, int modulo)
{
int *array = calloc(length ,sizeof(int));
for(int i = 0; i < length; i++)
{
array[i] = rand() % modulo;
}
return array;
}
int QsortIntCompare(const void *a, const void *b)
{
int arg1 = *(const int*)a;
int arg2 = *(const int*)b;
if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;
return 0;
}
int FindArraySum(int length, int *array)
{
int sum = 0;
for(int i = 0; i < length; i++)
{
assert(array[i] > -1);
sum += array[i];
}
return sum;
}
void CountCompositions(mpz_t compositions2, int integer, int parts)
{
//Find the binomial coefficient for (n+k-1, k-1) where n = integer, k = parts
mpz_bin_uiui(compositions2, integer + parts - 1, parts - 1);
}
void IndexToWeakComposition(mpz_t index, mpz_t low, mpz_t binomialCoefficent, mpz_t temp0, int integer, int parts, int *array)
{
assert(mpz_cmp_si(index,-1) > 0);
mpz_set_ui(low, 0);
int highestValue = integer;
int currentValue = 0;
for(int i = 0; i < parts; i++)
{
for(int j = 0; j <= highestValue; j++)
{
mpz_bin_uiui(binomialCoefficent, highestValue + parts - 2 - i - j, parts - 2- i);
mpz_add(temp0, low,binomialCoefficent);
if(mpz_cmp(temp0, index) > 0)
{
currentValue = j;
array[i] = j;
break;
}
mpz_add(low,low,binomialCoefficent);
}
highestValue -= currentValue;
}
}
int Test0()
{
srand(24515);
mpz_t compositions2,index, low, binomialCoefficent,temp0;
mpz_inits(compositions2, index, low, binomialCoefficent,temp0, NULL);
int length = 15;
int modulo = 10;
//Generate a finite set
int *finiteSet = RandomPositiveArray(length, modulo);assert(finiteSet != NULL);
//Sort the set
qsort(finiteSet, length, sizeof(int), QsortIntCompare);
//Find sum
int totalPossibleSum = FindArraySum(length, finiteSet);
//Count possible 2-compositions
CountCompositions(compositions2, totalPossibleSum, 2);
int *compositionHolder2 = calloc(2, sizeof(int));
mpz_tdiv_q_2exp(index, compositions2, 1); //Divide compositions2 by 2 to get the closestsum index
IndexToWeakComposition(index, low, binomialCoefficent, temp0, totalPossibleSum, 2, compositionHolder2);
PrintIntArray(length, finiteSet);
gmp_printf("%Zd possible ways to split %d. Best split is : %d %d\n", compositions2, totalPossibleSum,compositionHolder2[0],compositionHolder2[1]);
Dictionary dictionary = CreateDictionary(length, finiteSet);
PrintDictionary(dictionary);
if(finiteSet){free(finiteSet);}free(compositionHolder2);
mpz_clears(compositions2, index, low, binomialCoefficent,temp0, NULL);
DeleteDictionary(dictionary);
return 0;
}
int main()
{
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment