uni

University stuff
git clone git://git.christosmarg.xyz/uni-assignments.git
Log | Files | Refs | README | LICENSE

kcombinations.c (3911B)


      1 #include "kcombinations.h"
      2 
      3 int get_n()
      4 {
      5     int N;
      6 
      7     do
      8     {
      9         system("clear||cls");
     10         printf("N (6 < N <= 49): ");
     11         scanf("%d", &N);
     12     } while (N <= 6 || N > 49);
     13 
     14     return N;
     15 }
     16 
     17 
     18 int get_k(int N)
     19 {
     20     int K;
     21 
     22     do
     23     {
     24         printf("K (K < N <= 49): ");
     25         scanf("%d", &K);
     26     } while (K >= N || K > 49);
     27 
     28     system("clear||cls");
     29     
     30     return K;
     31 }
     32 
     33 
     34 void x_pair(int *x1, int *x2)
     35 {
     36     do
     37     {
     38         printf("x1: ");
     39         scanf("%d", x1);
     40         printf("x2: ");
     41         scanf("%d", x2);
     42     } while (*x1 < 0 || *x1 > *x2 || *x2 > 6);
     43 }
     44 
     45 
     46 void y_pair(int *y1, int *y2)
     47 {
     48     do
     49     {
     50         printf("y1: ");
     51         scanf("%d", y1);
     52         printf("y2: ");
     53         scanf("%d", y2);
     54     } while (*y1 < 21 || *y1 > *y2 || *y2 > 279);
     55 }
     56 
     57 
     58 void print_combs(int *arr, int N, int K, int x1, int x2, int y1, int y2)
     59 {
     60     int *currComb = (int *)malloc(N * sizeof(int));
     61 	int *freqArr = (int *)malloc(N * sizeof(int));
     62 	int unFrstCond = 0, unScndCondOnly = 0, printed = 0;
     63 
     64     if (currComb == NULL)
     65     {
     66         set_color(BOLD_RED);
     67         printf("Error! Not enough memory, exiting...\n");
     68         exit(EXIT_FAILURE);
     69         set_color(STANDARD);
     70     }
     71     else
     72     {    
     73         combinations(arr, currComb, freqArr, 0, N-1, 0, N, K, &printed, &unFrstCond, &unScndCondOnly, x1, x2, y1, y2);
     74         print_other(N, K, unFrstCond, unScndCondOnly, printed, arr, freqArr);
     75     }
     76 
     77     free(currComb);
     78 	free(freqArr);
     79 }
     80 
     81 
     82 void combinations(int *arr, int *currComb, int *freqArr, int start, int end, int index, int N, int K, int *printed, int *unFrstCond, int *unScndCondOnly, int x1, int x2, int y1, int y2) 
     83 {
     84     int i, j;
     85     
     86     if (index == K) 
     87     { 
     88         for (j = 0; j < K; j++) 
     89         {
     90             if (even_calc(currComb, K, x1, x2) && sum_comb_calc(currComb, K, y1, y2))
     91             {
     92                 printf("%d ", *(currComb + j));
     93                 if (j == K - 1)
     94 				{
     95 					frequency(freqArr, currComb, arr, N, K);
     96 					(*printed)++;
     97 					printf("\n");
     98 				}
     99             }
    100         }
    101         if (!even_calc(currComb, K, x1, x2) && sum_comb_calc(currComb, K, y1, y2)) (*unFrstCond)++;
    102         if (!sum_comb_calc(currComb, K, y1, y2)) (*unScndCondOnly)++;
    103         return;
    104     } 
    105 
    106     for (i = start; i <= end && end-i+1 >= K-index; i++) 
    107     { 
    108         *(currComb + index) = *(arr + i);
    109         combinations(arr, currComb, freqArr, i+1, end, index+1, N, K, printed, unFrstCond, unScndCondOnly, x1, x2, y1, y2); 
    110     }
    111 }
    112 
    113 
    114 bool even_calc(int *arr, int K, int x1, int x2)
    115 {
    116     int numEven = 0, i;
    117 
    118     for (i = 0; i < K; i++)
    119         if (*(arr + i) % 2 == 0) numEven++;
    120 
    121     return (numEven >= x1 && numEven <= x2) ? true : false;
    122 }
    123 
    124 
    125 bool sum_comb_calc(int *arr, int K, int y1, int y2)
    126 {
    127     int sumNums = 0, i;
    128 
    129     for (i = 0; i < K; i++)
    130         sumNums += *(arr + i);
    131     
    132     return (sumNums >= y1 && sumNums <= y2) ? true : false;
    133 }
    134 
    135 
    136 void frequency(int *freqArr, int *currComb, int *arr, int N, int K)
    137 {
    138 	int pos, i;
    139 
    140 	for (i = 0; i < K; i++)
    141 	{
    142 		pos = find_pos(arr, N, *(currComb + i));
    143 		(*(freqArr + pos))++;
    144 	}
    145 }
    146 
    147 
    148 long int combinations_count(int N, int K)
    149 {
    150     return (factorial(N) / (factorial(K) * factorial(N - K)));
    151 }
    152 
    153 
    154 long double factorial(int num)
    155 {
    156     int i;
    157     long double fac;
    158     if (num == 0) return -1;
    159     else for (i = 1, fac = 1; i <= num; i++) fac *= i;
    160     return fac;
    161 }
    162 
    163 
    164 void print_other(int N, int K, int unFrstCond, int unScndCondOnly, int printed, int *arr, int *freqArr)
    165 {
    166     int i;
    167 	
    168 	printf("\nTotal number of combinations %d to %d: %ld\n", N, K, combinations_count(N, K));
    169     printf("Number of combinations not satisfying the first condition: %d\n", unFrstCond);
    170     printf("Number of combinations not satisfying the second condition only: %d\n", unScndCondOnly);
    171     printf("Printed combinations: %d\n\n", printed);
    172 
    173 	for (i = 0; i < N; i++)
    174 		printf("%d appeared %d times\n", *(arr + i), *(freqArr + i));
    175 }