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 }