Created
July 12, 2025 06:59
-
-
Save MurageKibicho/9618d620ef7e4d71d3401b58445e59c8 to your computer and use it in GitHub Desktop.
Using LibGMP to enumerate integer compositions
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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