Combinatorial Number System Greedy

Kibicho Murage

·

Follow

Nov 11, 2021

--

Listen

Share

#include <stdio.h>
#include <stdlib.h>long NchooseK(int n, int k)
{
 long result = 1;
 if(n < k)
 {
  return 0;
 }
 if(n == k)
 {
  return 1;
 }
 if(k > n-k)
 {
  k = n - k;
 }
 for(int i = 0; i< k; i++)
 {
  result *= (n - i);
  result /= (i + 1);
 }
 return result;
}//Idk why I have to subtract 2
int FindLargestN(long number, int base)
{
 long highestValue = 0;
 int index = 1;
 while(highestValue <= number)
 {
  highestValue = NchooseK(index, base);
  index++;
 }
 return (index - 2);
}void GreedyCombinatorial(long number, int base)
{
 int startN = FindLargestN(number,base);
 while(number >= 0)
 {
  printf("%d %d\n",startN, base);
  number -= (NchooseK(startN, base));
  base--;
  startN = FindLargestN(number, base);
 }
}int main()
{
 GreedyCombinatorial(9876, 123);
 return 0;
}