Rewrite this function in C. You can assume that the input is a 2d matrix correctly formatted. Call it rref(int** matrix, int rows, int cols, int graphlen) where the size is matrix[rows][cols]. Return an int** of used_for_row. def rref(matrix, graphlen): PH = 16 extra = 0 col = 0 pivots = [] used_for_row = [set([i]) for i in range(matrix.shape[0])] matrix = matrix%PH while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]: if matrix[col,col+extra] == 0: if np.all(matrix[:,col] == 0): extra += 1 continue other = np.argwhere(matrix[:,col+extra] != 0).flatten()[-1] if other < col: extra += 1 continue matrix[col], matrix[other] = list(matrix[other]), list(matrix[col]) used_for_row[col], used_for_row[other] = used_for_row[other], used_for_row[col] pivots.append(col+extra) pivot = matrix[col,col+extra] if col+extra < graphlen: assert np.abs(pivot) == 1 or np.abs(pivot) == PH-1 else: assert np.abs(pivot) == 2 or np.abs(pivot) == PH-2 pivot //= 2 matrix[col] *= pivot matrix[col] %= PH others = np.argwhere(matrix[:,col+extra]).flatten() for i in others: if i == col: continue used_for_row[i] |= used_for_row[col] if col < graphlen: matrix[i] -= matrix[col]*matrix[i,col+extra] else: while matrix[i,col+extra] != 0: matrix[i] = (matrix[i]-matrix[col])%PH matrix[i] %= PH col += 1 matrix = np.array(matrix)%PH return [sorted(x) for x in used_for_row]
Rewrite this function in C. You can assume that the input is a 2d matrix correctly formatted. Call it rref(int** matrix, int rows, int cols, int graphlen) where the size is matrix[rows][cols]. Return an int** of used_for_row. def rref(matrix, graphlen): PH = 16 extra = 0 col = 0 pivots = [] used_for_row = [set([i]) for i in range(matrix.shape[0])] matrix = matrix%PH while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]: if matrix[col,col+extra] == 0: if np.all(matrix[:,col] == 0): extra += 1 continue other = np.argwhere(matrix[:,col+extra] != 0).flatten()[-1] if other < col: extra += 1 continue matrix[col], matrix[other] = list(matrix[other]), list(matrix[col]) used_for_row[col], used_for_row[other] = used_for_row[other], used_for_row[col] pivots.append(col+extra) pivot = matrix[col,col+extra] if col+extra < graphlen: assert np.abs(pivot) == 1 or np.abs(pivot) == PH-1 else: assert np.abs(pivot) == 2 or np.abs(pivot) == PH-2 pivot //= 2 matrix[col] *= pivot matrix[col] %= PH others = np.argwhere(matrix[:,col+extra]).flatten() for i in others: if i == col: continue used_for_row[i] |= used_for_row[col] if col < graphlen: matrix[i] -= matrix[col]*matrix[i,col+extra] else: while matrix[i,col+extra] != 0: matrix[i] = (matrix[i]-matrix[col])%PH matrix[i] %= PH col += 1 matrix = np.array(matrix)%PH return [sorted(x) for x in used_for_row]
Below is one acceptable C‐version. (You are free to change the details of memory management and helper functions.) In this version we keep for each row a “set” implemented as an array of ints (with worst–case capacity “rows”) together with a count. (After performing all the operations we sort each row’s set, so that the final answer corresponds roughly to Python’s “sorted(x)” for each row.) You can assume that the input “matrix” is an array of “rows” pointers (each of length “cols”). One may also wish to modify the code so that the “used_for_row” information is returned together with its sizes. Below is the complete code: ------------------------------------------------ /* rref.c */ #include <stdio.h> #include <stdlib.h> #include <assert.h> #define PH 16 /* Comparison function for qsort (used to sort each “set”) */ int cmp_int(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return int_a - int_b; } /* Helper: try to add value “val” to the set given by dest[0..*dest_count-1] (dest has capacity cap). If already present, do nothing. (For simplicity we assume cap is at least “rows”.) */ void union_value(int *dest, int *dest_count, int val) { int found = 0; for(int i = 0; i < *dest_count; i++){ if(dest[i] == val) { found = 1; break; } } if(!found) { dest[(*dest_count)++] = val; } } /* rref computes a reduced–row–echelon–form like transformation on “matrix” modulo PH (16) and simultaneously computes for each row a set (as an array of integers) of row–indices that “contributed” (initially each row contains its own index). graphlen is used to choose the arithmetic rules. Input: matrix – an int** of size [rows][cols] rows, cols – dimensions of matrix graphlen – used to decide which arithmetic rule to apply. Returns: an int** in which row i is an array (of length at most rows) of the sorted integers that were “used_for_row”. (For a complete solution you might also return the set sizes.) */ int** rref(int** matrix, int rows, int cols, int graphlen) { int extra = 0; int col = 0; int pivot_index; /* For recording pivot positions (not used later) */ int* pivots = (int*) malloc(rows * sizeof(int)); int pivot_count = 0; /* Allocate an array “used” with one int* per row and a parallel count. We allocate capacity “rows” for each row. */ int **used = (int**) malloc(rows * sizeof(int*)); int *used_count = (int*) malloc(rows * sizeof(int)); int capacity = rows; // worst-case capacity for(int i = 0; i < rows; i++){ used[i] = (int*) malloc(capacity * sizeof(int)); used[i][0] = i; // start with {i} used_count[i] = 1; } /* First, reduce all entries modulo PH */ for(int i = 0; i < rows; i++){ for(int j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } while((col + extra) < (cols - 1) && col < rows) { /* If the pivot candidate is zero, try to swap with a row below */ if(matrix[col][col + extra] == 0){ /* If the entire column “col” (or you might expect col+extra) is zero then bump extra. (The Python code checks np.all(matrix[:,col]==0).) */ int all_zero = 1; for(int i = 0; i < rows; i++){ if(matrix[i][col] != 0) { all_zero = 0; break; } } if(all_zero) { extra++; continue; } /* Find the last row “other” where the candidate entry in column (col+extra) is nonzero */ int other = -1; for(int i = 0; i < rows; i++){ if(matrix[i][col + extra] != 0) other = i; } if(other < col) { extra++; continue; } /* Swap rows col and other in matrix */ { int *tmp = matrix[col]; matrix[col] = matrix[other]; matrix[other] = tmp; } /* Swap their used sets */ { int *tmp_used = used[col]; used[col] = used[other]; used[other] = tmp_used; int tmp_count = used_count[col]; used_count[col] = used_count[other]; used_count[other] = tmp_count; } } /* Record the pivot column index */ pivots[pivot_count++] = col + extra; int pivot = matrix[col][col + extra]; if((col + extra) < graphlen) { int abs_pivot = (pivot < 0 ? -pivot : pivot); /* In this branch, we expect pivot to be ±1 modulo PH */ assert(abs_pivot == 1 || abs_pivot == (PH - 1)); } else { int abs_pivot = (pivot < 0 ? -pivot : pivot); /* In this branch, we expect pivot to be ±2 modulo PH */ assert(abs_pivot == 2 || abs_pivot == (PH - 2)); pivot /= 2; // divide by 2 (assumed to divide evenly) } /* Scale row “col” so that the pivot becomes 1. Multiply each entry in row col by “pivot” modulo PH. */ for(int j = 0; j < cols; j++){ matrix[col][j] = (matrix[col][j] * pivot) % PH; if(matrix[col][j] < 0) matrix[col][j] += PH; } /* For each other row i in which column (col+extra) is nonzero, zero out the entry in that column. Also union the “used_for_row” sets. */ for(int i = 0; i < rows; i++){ if(i == col) continue; if(matrix[i][col + extra] != 0) { /* Union: add every element from used[col] into used[i] */ for (int k = 0; k < used_count[col]; k++){ union_value(used[i], &used_count[i], used[col][k]); } if(col < graphlen) { int factor = matrix[i][col + extra]; /* Row i = row i - factor * row col */ for(int j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - factor * matrix[col][j]) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } else { /* While the (col+extra) entry is nonzero, subtract row col once */ while(matrix[i][col + extra] != 0) { for(int j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - matrix[col][j]) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } /* Make sure row i’s entries are modulo PH */ for(int j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } col++; } /* Final cleanup: enforce all entries mod PH (may be redundant) */ for(int i = 0; i < rows; i++){ for(int j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } /* Sort the “used” sets for each row. (For a complete solution you might wish to also return their sizes.) */ for(int i = 0; i < rows; i++){ qsort(used[i], used_count[i], sizeof(int), cmp_int); } /* Free temporary allocations that are not needed after return */ free(pivots); free(used_count); return used; } ////////////////// // Example usage: ////////////////// #ifdef EXAMPLE_MAIN int main(void) { int rows = 3, cols = 5, graphlen = 3; // Example: allocate a 3x5 matrix (dynamically allocated rows). int **matrix = (int **) malloc(rows * sizeof(int *)); for (int i = 0; i < rows; i++){ matrix[i] = (int *) malloc(cols * sizeof(int)); } // Fill the matrix with some example values. // (In an actual use you would fill in a correctly‐formatted matrix.) int ex[3][5] = { { 1, 2, 3, 4, 5 }, { 0, 1, 0, 2, 3 }, { 0, 0, 1, 1, 1 } }; for (int i = 0; i < rows; i++){ for (int j = 0; j < cols; j++){ matrix[i][j] = ex[i][j]; } } int **used = rref(matrix, rows, cols, graphlen); // Print the used sets for each row. for (int i = 0; i < rows; i++){ printf("Row %d used: ", i); // We do not track the size here; in a production code you might want to // modify rref to also return the sizes. // For demonstration, we assume the maximum size is “rows” and print non-negative values. for (int j = 0; j < rows; j++){ // Here we assume that our “set” does not contain duplicates and unused space is left uninitialized. // In a complete implementation you would also have a count per row. printf("%d ", used[i][j]); } printf("\n"); } // Free allocated memory. for (int i = 0; i < rows; i++){ free(matrix[i]); free(used[i]); } free(matrix); free(used); return 0; } #endif ------------------------------------------------ Explanation of key points: 1. We first reduce every matrix entry mod PH. 2. For each pivot position (row col with an “extra” offset), • If the candidate is zero, we try to swap with another row. • We record the pivot column index. 3. We then scale the pivot row so that its pivot becomes 1 (taking into account different arithmetic when col+extra < graphlen versus not). 4. Then for every other row with a nonzero entry in the pivot column, we subtract an appropriate multiple (or repeatedly subtract in the second case) so that the pivot entry becomes 0 and we “union” the used–row set. 5. Finally we sort each used–row set and return the jagged int**. This solution is one way to “translate” the given Python rref function into C.
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 | /* rref.c */ #include <stdio.h> #include <stdlib.h> #include <assert.h> #define PH 16 /* Comparison function for qsort (used to sort each “set”) */ int cmp_int(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return int_a - int_b; } /* Helper: try to add value “val” to the set given by dest[0..*dest_count-1] (dest has capacity cap). If already present, do nothing. (For simplicity we assume cap is at least “rows”.) */ void union_value(int *dest, int *dest_count, int val) { int found = 0; for(int i = 0; i < *dest_count; i++){ if(dest[i] == val) { found = 1; break; } } if(!found) { dest[(*dest_count)++] = val; } } /* rref computes a reduced–row–echelon–form like transformation on “matrix” modulo PH (16) and simultaneously computes for each row a set (as an array of integers) of row–indices that “contributed” (initially each row contains its own index). graphlen is used to choose the arithmetic rules. Input: matrix – an int** of size [rows][cols] rows, cols – dimensions of matrix graphlen – used to decide which arithmetic rule to apply. Returns: an int** in which row i is an array (of length at most rows) of the sorted integers that were “used_for_row”. (For a complete solution you might also return the set sizes.) */ int** rref(int** matrix, int rows, int cols, int graphlen) { int extra = 0; int col = 0; int pivot_index; /* For recording pivot positions (not used later) */ int* pivots = (int*) malloc(rows * sizeof(int)); int pivot_count = 0; /* Allocate an array “used” with one int* per row and a parallel count. We allocate capacity “rows” for each row. */ int **used = (int**) malloc(rows * sizeof(int*)); int *used_count = (int*) malloc(rows * sizeof(int)); int capacity = rows; // worst-case capacity for(int i = 0; i < rows; i++){ used[i] = (int*) malloc(capacity * sizeof(int)); used[i][0] = i; // start with {i} used_count[i] = 1; } /* First, reduce all entries modulo PH */ for(int i = 0; i < rows; i++){ for(int j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } while((col + extra) < (cols - 1) && col < rows) { /* If the pivot candidate is zero, try to swap with a row below */ if(matrix[col][col + extra] == 0){ /* If the entire column “col” (or you might expect col+extra) is zero then bump extra. (The Python code checks np.all(matrix[:,col]==0).) */ int all_zero = 1; for(int i = 0; i < rows; i++){ if(matrix[i][col] != 0) { all_zero = 0; break; } } if(all_zero) { extra++; continue; } /* Find the last row “other” where the candidate entry in column (col+extra) is nonzero */ int other = -1; for(int i = 0; i < rows; i++){ if(matrix[i][col + extra] != 0) other = i; } if(other < col) { extra++; continue; } /* Swap rows col and other in matrix */ { int *tmp = matrix[col]; matrix[col] = matrix[other]; matrix[other] = tmp; } /* Swap their used sets */ { int *tmp_used = used[col]; used[col] = used[other]; used[other] = tmp_used; int tmp_count = used_count[col]; used_count[col] = used_count[other]; used_count[other] = tmp_count; } } /* Record the pivot column index */ pivots[pivot_count++] = col + extra; int pivot = matrix[col][col + extra]; if((col + extra) < graphlen) { int abs_pivot = (pivot < 0 ? -pivot : pivot); /* In this branch, we expect pivot to be ±1 modulo PH */ assert(abs_pivot == 1 || abs_pivot == (PH - 1)); } else { int abs_pivot = (pivot < 0 ? -pivot : pivot); /* In this branch, we expect pivot to be ±2 modulo PH */ assert(abs_pivot == 2 || abs_pivot == (PH - 2)); pivot /= 2; // divide by 2 (assumed to divide evenly) } /* Scale row “col” so that the pivot becomes 1. Multiply each entry in row col by “pivot” modulo PH. */ for(int j = 0; j < cols; j++){ matrix[col][j] = (matrix[col][j] * pivot) % PH; if(matrix[col][j] < 0) matrix[col][j] += PH; } /* For each other row i in which column (col+extra) is nonzero, zero out the entry in that column. Also union the “used_for_row” sets. */ for(int i = 0; i < rows; i++){ if(i == col) continue; if(matrix[i][col + extra] != 0) { /* Union: add every element from used[col] into used[i] */ for (int k = 0; k < used_count[col]; k++){ union_value(used[i], &used_count[i], used[col][k]); } if(col < graphlen) { int factor = matrix[i][col + extra]; /* Row i = row i - factor * row col */ for(int j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - factor * matrix[col][j]) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } else { /* While the (col+extra) entry is nonzero, subtract row col once */ while(matrix[i][col + extra] != 0) { for(int j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - matrix[col][j]) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } /* Make sure row i’s entries are modulo PH */ for(int j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } col++; } /* Final cleanup: enforce all entries mod PH (may be redundant) */ for(int i = 0; i < rows; i++){ for(int j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } /* Sort the “used” sets for each row. (For a complete solution you might wish to also return their sizes.) */ for(int i = 0; i < rows; i++){ qsort(used[i], used_count[i], sizeof(int), cmp_int); } /* Free temporary allocations that are not needed after return */ free(pivots); free(used_count); return used; } |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 | /* rref.c */ #include <stdio.h> #include <stdlib.h> #include <assert.h> #define PH 16 /* Comparison function for qsort (used to sort each “set”) */ int cmp_int(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return int_a - int_b; } /* Helper: try to add value “val” to the set given by dest[0..*dest_count-1] (dest has capacity cap). If already present, do nothing. (For simplicity we assume cap is at least “rows”.) */ void union_value(int *dest, int *dest_count, int val) { int found = 0; for(int i = 0; i < *dest_count; i++){ if(dest[i] == val) { found = 1; break; } } if(!found) { dest[(*dest_count)++] = val; } } /* rref computes a reduced–row–echelon–form like transformation on “matrix” modulo PH (16) and simultaneously computes for each row a set (as an array of integers) of row–indices that “contributed” (initially each row contains its own index). graphlen is used to choose the arithmetic rules. Input: matrix – an int** of size [rows][cols] rows, cols – dimensions of matrix graphlen – used to decide which arithmetic rule to apply. Returns: an int** in which row i is an array (of length at most rows) of the sorted integers that were “used_for_row”. (For a complete solution you might also return the set sizes.) */ int** rref(int** matrix, int rows, int cols, int graphlen) { int extra = 0; int col = 0; int pivot_index; /* For recording pivot positions (not used later) */ int* pivots = (int*) malloc(rows * sizeof(int)); int pivot_count = 0; /* Allocate an array “used” with one int* per row and a parallel count. We allocate capacity “rows” for each row. */ int **used = (int**) malloc(rows * sizeof(int*)); int *used_count = (int*) malloc(rows * sizeof(int)); int capacity = rows; // worst-case capacity for(int i = 0; i < rows; i++){ used[i] = (int*) malloc(capacity * sizeof(int)); used[i][0] = i; // start with {i} used_count[i] = 1; } /* First, reduce all entries modulo PH */ for(int i = 0; i < rows; i++){ for(int j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } while((col + extra) < (cols - 1) && col < rows) { /* If the pivot candidate is zero, try to swap with a row below */ if(matrix[col][col + extra] == 0){ /* If the entire column “col” (or you might expect col+extra) is zero then bump extra. (The Python code checks np.all(matrix[:,col]==0).) */ int all_zero = 1; for(int i = 0; i < rows; i++){ if(matrix[i][col] != 0) { all_zero = 0; break; } } if(all_zero) { extra++; continue; } /* Find the last row “other” where the candidate entry in column (col+extra) is nonzero */ int other = -1; for(int i = 0; i < rows; i++){ if(matrix[i][col + extra] != 0) other = i; } if(other < col) { extra++; continue; } /* Swap rows col and other in matrix */ { int *tmp = matrix[col]; matrix[col] = matrix[other]; matrix[other] = tmp; } /* Swap their used sets */ { int *tmp_used = used[col]; used[col] = used[other]; used[other] = tmp_used; int tmp_count = used_count[col]; used_count[col] = used_count[other]; used_count[other] = tmp_count; } } /* Record the pivot column index */ pivots[pivot_count++] = col + extra; int pivot = matrix[col][col + extra]; if((col + extra) < graphlen) { int abs_pivot = (pivot < 0 ? -pivot : pivot); /* In this branch, we expect pivot to be ±1 modulo PH */ assert(abs_pivot == 1 || abs_pivot == (PH - 1)); } else { int abs_pivot = (pivot < 0 ? -pivot : pivot); /* In this branch, we expect pivot to be ±2 modulo PH */ assert(abs_pivot == 2 || abs_pivot == (PH - 2)); pivot /= 2; // divide by 2 (assumed to divide evenly) } /* Scale row “col” so that the pivot becomes 1. Multiply each entry in row col by “pivot” modulo PH. */ for(int j = 0; j < cols; j++){ matrix[col][j] = (matrix[col][j] * pivot) % PH; if(matrix[col][j] < 0) matrix[col][j] += PH; } /* For each other row i in which column (col+extra) is nonzero, zero out the entry in that column. Also union the “used_for_row” sets. */ for(int i = 0; i < rows; i++){ if(i == col) continue; if(matrix[i][col + extra] != 0) { /* Union: add every element from used[col] into used[i] */ for (int k = 0; k < used_count[col]; k++){ union_value(used[i], &used_count[i], used[col][k]); } if(col < graphlen) { int factor = matrix[i][col + extra]; /* Row i = row i - factor * row col */ for(int j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - factor * matrix[col][j]) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } else { /* While the (col+extra) entry is nonzero, subtract row col once */ while(matrix[i][col + extra] != 0) { for(int j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - matrix[col][j]) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } /* Make sure row i’s entries are modulo PH */ for(int j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } col++; } /* Final cleanup: enforce all entries mod PH (may be redundant) */ for(int i = 0; i < rows; i++){ for(int j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } /* Sort the “used” sets for each row. (For a complete solution you might wish to also return their sizes.) */ for(int i = 0; i < rows; i++){ qsort(used[i], used_count[i], sizeof(int), cmp_int); } /* Free temporary allocations that are not needed after return */ free(pivots); free(used_count); return used; } #include<stdio.h> #include<stdlib.h> int main() { int arr0[] = {1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}; int arr1[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr2[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -20}; int arr3[] = {0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, -20}; int arr4[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr5[] = {0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr6[] = {0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0}; int arr7[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, -30}; int arr8[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr9[] = {0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, -20}; int arr10[] = {1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}; int arr11[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr12[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr13[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -14}; int arr14[] = {0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr15[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, -30}; int arr16[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr17[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr18[] = {0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr19[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13}; int arr20[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr21[] = {0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr22[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, -20}; int arr23[] = {0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr24[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr25[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13}; int arr26[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr27[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13}; int arr28[] = {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr29[] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr30[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr31[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr32[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, -10}; int arr33[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13}; int arr34[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr35[] = {0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -9}; int arr36[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, -20}; int arr37[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, -40}; int arr38[] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int* arr[] = {arr0, arr1, arr2, arr3, arr4, arr5, arr6, arr7, arr8, arr9, arr10, arr11, arr12, arr13, arr14, arr15, arr16, arr17, arr18, arr19, arr20, arr21, arr22, arr23, arr24, arr25, arr26, arr27, arr28, arr29, arr30, arr31, arr32, arr33, arr34, arr35, arr36, arr37, arr38}; int** got = rref(arr, 39, 49, 37); int answer = got[3][0]+got[3][1]+got[3][2]+got[3][3]+got[3][4]+got[3][5]+got[3][6]; int expected = 146; if (answer != expected) { printf("Wrong answer; got %d instead of %d.\n", answer, expected); exit(1); } printf("All tests passed\n"); } |
All tests passed
Testing if the previous output contains the string All tests passed: True
Rewrite this function in C. You can assume that the input is a 2d matrix correctly formatted. Call it rref(int** matrix, int rows, int cols, int graphlen) where the size is matrix[rows][cols]. Return an int** of used_for_row. def rref(matrix, graphlen): PH = 16 extra = 0 col = 0 pivots = [] used_for_row = [set([i]) for i in range(matrix.shape[0])] matrix = matrix%PH while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]: if matrix[col,col+extra] == 0: if np.all(matrix[:,col] == 0): extra += 1 continue other = np.argwhere(matrix[:,col+extra] != 0).flatten()[-1] if other < col: extra += 1 continue matrix[col], matrix[other] = list(matrix[other]), list(matrix[col]) used_for_row[col], used_for_row[other] = used_for_row[other], used_for_row[col] pivots.append(col+extra) pivot = matrix[col,col+extra] if col+extra < graphlen: assert np.abs(pivot) == 1 or np.abs(pivot) == PH-1 else: assert np.abs(pivot) == 2 or np.abs(pivot) == PH-2 pivot //= 2 matrix[col] *= pivot matrix[col] %= PH others = np.argwhere(matrix[:,col+extra]).flatten() for i in others: if i == col: continue used_for_row[i] |= used_for_row[col] if col < graphlen: matrix[i] -= matrix[col]*matrix[i,col+extra] else: while matrix[i,col+extra] != 0: matrix[i] = (matrix[i]-matrix[col])%PH matrix[i] %= PH col += 1 matrix = np.array(matrix)%PH return [sorted(x) for x in used_for_row]
Rewrite this function in C. You can assume that the input is a 2d matrix correctly formatted. Call it rref(int** matrix, int rows, int cols, int graphlen) where the size is matrix[rows][cols]. Return an int** of used_for_row. def rref(matrix, graphlen): PH = 16 extra = 0 col = 0 pivots = [] used_for_row = [set([i]) for i in range(matrix.shape[0])] matrix = matrix%PH while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]: if matrix[col,col+extra] == 0: if np.all(matrix[:,col] == 0): extra += 1 continue other = np.argwhere(matrix[:,col+extra] != 0).flatten()[-1] if other < col: extra += 1 continue matrix[col], matrix[other] = list(matrix[other]), list(matrix[col]) used_for_row[col], used_for_row[other] = used_for_row[other], used_for_row[col] pivots.append(col+extra) pivot = matrix[col,col+extra] if col+extra < graphlen: assert np.abs(pivot) == 1 or np.abs(pivot) == PH-1 else: assert np.abs(pivot) == 2 or np.abs(pivot) == PH-2 pivot //= 2 matrix[col] *= pivot matrix[col] %= PH others = np.argwhere(matrix[:,col+extra]).flatten() for i in others: if i == col: continue used_for_row[i] |= used_for_row[col] if col < graphlen: matrix[i] -= matrix[col]*matrix[i,col+extra] else: while matrix[i,col+extra] != 0: matrix[i] = (matrix[i]-matrix[col])%PH matrix[i] %= PH col += 1 matrix = np.array(matrix)%PH return [sorted(x) for x in used_for_row]
Below is one acceptable C‐implementation. In this version we assume that “matrix” is given as an array of rows (each row an int array of length cols) and that the caller will free the returned arrays when finished. (Also note that the “used_for_row” “sets” are implemented as a Boolean array of length “rows” for each row; then the final output is an array of sorted (increasing) indices in a dynamically‐allocated array for each row.) You may need to adjust memory–management and error–handling to suit your application. Below is the complete C code for the rref function: ------------------------------------------------------------ #include <stdio.h> #include <stdlib.h> #include <assert.h> #define PH 16 // rref: Given a rows x cols matrix with modulo arithmetic modulo PH, // perform a reduction algorithm (as in the Python code) and return an // array used_for_row such that used_for_row[i] is a sorted list (ascending) // of the indices (from 0 to rows-1) that were “used” for row i. // // The parameter graphlen is used to decide which assertions and modifications // are performed on the pivot. int** rref(int** matrix, int rows, int cols, int graphlen) { int i, j; int extra = 0; int col = 0; // Allocate a 2D “boolean” array to keep track of the used rows. // Each used_for_row[i] is an integer array of length 'rows', holding 0/1. int **used_for_row = malloc(rows * sizeof(int*)); if (!used_for_row) exit(EXIT_FAILURE); for(i = 0; i < rows; i++){ used_for_row[i] = calloc(rows, sizeof(int)); if (!used_for_row[i]) exit(EXIT_FAILURE); used_for_row[i][i] = 1; // Initially, each row just “uses itself” } // First, reduce every entry modulo PH. for(i = 0; i < rows; i++){ for(j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } // Main loop. (In Python: while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]) while ((col + extra) < (cols - 1) && col < rows) { // If the pivot candidate is 0 if(matrix[col][col + extra] == 0) { // Check if entire column (at index col) is 0. int allZero = 1; for(i = 0; i < rows; i++){ if(matrix[i][col] != 0) { allZero = 0; break; } } if(allZero) { extra++; continue; // skip the rest of the loop } // Look for another row in which the (col+extra)-th entry is nonzero. int other = -1; for(i = 0; i < rows; i++){ if(matrix[i][col+extra] != 0) other = i; // take the last such row found } if(other < col) { extra++; continue; } // Swap row 'col' with row 'other' in both matrix and used_for_row. { int *temp_row = matrix[col]; matrix[col] = matrix[other]; matrix[other] = temp_row; int *temp_used = used_for_row[col]; used_for_row[col] = used_for_row[other]; used_for_row[other] = temp_used; } } // Here we have a nonzero pivot in matrix[col][col+extra]. int pivot = matrix[col][col+extra]; if ((col + extra) < graphlen) { // The python code asserts: abs(pivot)==1 or abs(pivot)==PH-1. if (!((abs(pivot) == 1) || (abs(pivot) == PH - 1))) { // For production code you may wish to handle this error. assert(0 && "Pivot value is not ±1 mod PH in the top block"); } } else { // For (col+extra) >= graphlen, we expect abs(pivot)==2 or PH-2. if (!((abs(pivot) == 2) || (abs(pivot) == PH - 2))) { assert(0 && "Pivot value is not ±2 mod PH in the bottom block"); } // Adjust the pivot as in the Python code. pivot = pivot / 2; } // Multiply row 'col' by pivot so that pivot becomes 1 modulo PH. for(j = 0; j < cols; j++){ matrix[col][j] = (matrix[col][j] * pivot) % PH; if(matrix[col][j] < 0) matrix[col][j] += PH; } // For every other row that has a nonzero entry in column (col+extra), // eliminate that entry. for(i = 0; i < rows; i++){ if(i == col) continue; if(matrix[i][col+extra] != 0){ // Union: update used_for_row[i] = used_for_row[i] ∪ used_for_row[col] for(j = 0; j < rows; j++){ if(used_for_row[col][j]) used_for_row[i][j] = 1; } if(col < graphlen) { // Operation: matrix[i] -= matrix[col] * (matrix[i][col+extra]) int factor = matrix[i][col+extra]; for(j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - matrix[col][j] * factor) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } else { // Operation: while (matrix[i][col+extra] != 0) while(matrix[i][col+extra] != 0){ for(j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - matrix[col][j]) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } // Ensure row i is in the proper modulo range. for(j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } col++; } // Final reduction: ensure every entry is in range [0, PH-1]. for(i = 0; i < rows; i++){ for(j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } // Now we convert the used_for_row boolean arrays into sorted lists. // For each row, count how many indices are present, allocate an int array, // and fill it with indices in increasing order. int **result = malloc(rows * sizeof(int*)); if (!result) exit(EXIT_FAILURE); for(i = 0; i < rows; i++){ int count = 0; for(j = 0; j < rows; j++){ if(used_for_row[i][j]) count++; } // Allocate an array for the indices. result[i] = malloc(count * sizeof(int)); if(!result[i]) exit(EXIT_FAILURE); int idx = 0; for(j = 0; j < rows; j++){ if(used_for_row[i][j]){ result[i][idx++] = j; } } // Because we examined indices from 0 to rows-1, they are already in increasing order. } // Free the temporary used_for_row boolean arrays. for(i = 0; i < rows; i++){ free(used_for_row[i]); } free(used_for_row); return result; } // Example usage: // // int main(void) // { // // For example, create a 3x4 matrix. // int rows = 3, cols = 4; // int **mat = malloc(rows * sizeof(int*)); // for (int i = 0; i < rows; i++) { // mat[i] = malloc(cols * sizeof(int)); // } // // // Fill the matrix with your data. // // Assume we have data that is already 2D formatted. // // ... // // int graphlen = 2; // or set appropriately // int **used = rref(mat, rows, cols, graphlen); // // // Print out used_for_row results. // for (int i = 0; i < rows; i++) { // // First, determine the number of entries (here, we must know or recompute count). // // For demonstration, we print all indices from 0 to rows-1 that are present. // printf("Row %d used indices: ", i); // for (int j = 0; j < rows; j++) { // // In this demo, we simply print the result array that was built in order. // // (In a full implementation you might also return the size for each row.) // // Here we assume that the caller keeps track of sizes separately. // } // printf("\n"); // free(used[i]); // } // free(used); // // // Also free matrix if needed. // for (int i = 0; i < rows; i++) { // free(mat[i]); // } // free(mat); // return 0; //} ------------------------------------------------------------ Explanation: 1. We define PH = 16. 2. We allocate a temporary “used_for_row” structure for each row as a Boolean array of size rows. Initially only the row’s own index is set. 3. We reduce every matrix entry modulo PH. 4. The main loop runs while (col + extra) is less than (cols – 1) and while col < rows. (Notice that “extra” is increased when a candidate pivot is zero.) 5. If the pivot candidate is 0 we try to swap in a row that has a nonzero value in that column. 6. Once a pivot is chosen, we “normalize” that row by multiplying by pivot so that the pivot becomes 1 modulo PH. (When col >= graphlen, the pivot value is “adjusted” by dividing by 2.) 7. We then eliminate nonzero entries in the pivot’s column in the other rows (using either a one–step subtraction or a while–loop subtraction, just as in the python code). As we do this we update used_for_row by taking the union of the Boolean arrays. 8. Finally we convert each Boolean array into an int array containing the sorted row indices. 9. We free our temporary “used_for_row” storage and return the result. This code is only one possible interpretation of the Python function’s logic in C. You may need to adjust the error handling (for example, how pivot‐value assertions are handled) and memory–management (for example, providing sizes for each returned array) for your specific application.
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 | #include <stdio.h> #include <stdlib.h> #include <assert.h> #define PH 16 // rref: Given a rows x cols matrix with modulo arithmetic modulo PH, // perform a reduction algorithm (as in the Python code) and return an // array used_for_row such that used_for_row[i] is a sorted list (ascending) // of the indices (from 0 to rows-1) that were “used” for row i. // // The parameter graphlen is used to decide which assertions and modifications // are performed on the pivot. int** rref(int** matrix, int rows, int cols, int graphlen) { int i, j; int extra = 0; int col = 0; // Allocate a 2D “boolean” array to keep track of the used rows. // Each used_for_row[i] is an integer array of length 'rows', holding 0/1. int **used_for_row = malloc(rows * sizeof(int*)); if (!used_for_row) exit(EXIT_FAILURE); for(i = 0; i < rows; i++){ used_for_row[i] = calloc(rows, sizeof(int)); if (!used_for_row[i]) exit(EXIT_FAILURE); used_for_row[i][i] = 1; // Initially, each row just “uses itself” } // First, reduce every entry modulo PH. for(i = 0; i < rows; i++){ for(j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } // Main loop. (In Python: while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]) while ((col + extra) < (cols - 1) && col < rows) { // If the pivot candidate is 0 if(matrix[col][col + extra] == 0) { // Check if entire column (at index col) is 0. int allZero = 1; for(i = 0; i < rows; i++){ if(matrix[i][col] != 0) { allZero = 0; break; } } if(allZero) { extra++; continue; // skip the rest of the loop } // Look for another row in which the (col+extra)-th entry is nonzero. int other = -1; for(i = 0; i < rows; i++){ if(matrix[i][col+extra] != 0) other = i; // take the last such row found } if(other < col) { extra++; continue; } // Swap row 'col' with row 'other' in both matrix and used_for_row. { int *temp_row = matrix[col]; matrix[col] = matrix[other]; matrix[other] = temp_row; int *temp_used = used_for_row[col]; used_for_row[col] = used_for_row[other]; used_for_row[other] = temp_used; } } // Here we have a nonzero pivot in matrix[col][col+extra]. int pivot = matrix[col][col+extra]; if ((col + extra) < graphlen) { // The python code asserts: abs(pivot)==1 or abs(pivot)==PH-1. if (!((abs(pivot) == 1) || (abs(pivot) == PH - 1))) { // For production code you may wish to handle this error. assert(0 && "Pivot value is not ±1 mod PH in the top block"); } } else { // For (col+extra) >= graphlen, we expect abs(pivot)==2 or PH-2. if (!((abs(pivot) == 2) || (abs(pivot) == PH - 2))) { assert(0 && "Pivot value is not ±2 mod PH in the bottom block"); } // Adjust the pivot as in the Python code. pivot = pivot / 2; } // Multiply row 'col' by pivot so that pivot becomes 1 modulo PH. for(j = 0; j < cols; j++){ matrix[col][j] = (matrix[col][j] * pivot) % PH; if(matrix[col][j] < 0) matrix[col][j] += PH; } // For every other row that has a nonzero entry in column (col+extra), // eliminate that entry. for(i = 0; i < rows; i++){ if(i == col) continue; if(matrix[i][col+extra] != 0){ // Union: update used_for_row[i] = used_for_row[i] ∪ used_for_row[col] for(j = 0; j < rows; j++){ if(used_for_row[col][j]) used_for_row[i][j] = 1; } if(col < graphlen) { // Operation: matrix[i] -= matrix[col] * (matrix[i][col+extra]) int factor = matrix[i][col+extra]; for(j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - matrix[col][j] * factor) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } else { // Operation: while (matrix[i][col+extra] != 0) while(matrix[i][col+extra] != 0){ for(j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - matrix[col][j]) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } // Ensure row i is in the proper modulo range. for(j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } col++; } // Final reduction: ensure every entry is in range [0, PH-1]. for(i = 0; i < rows; i++){ for(j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } // Now we convert the used_for_row boolean arrays into sorted lists. // For each row, count how many indices are present, allocate an int array, // and fill it with indices in increasing order. int **result = malloc(rows * sizeof(int*)); if (!result) exit(EXIT_FAILURE); for(i = 0; i < rows; i++){ int count = 0; for(j = 0; j < rows; j++){ if(used_for_row[i][j]) count++; } // Allocate an array for the indices. result[i] = malloc(count * sizeof(int)); if(!result[i]) exit(EXIT_FAILURE); int idx = 0; for(j = 0; j < rows; j++){ if(used_for_row[i][j]){ result[i][idx++] = j; } } // Because we examined indices from 0 to rows-1, they are already in increasing order. } // Free the temporary used_for_row boolean arrays. for(i = 0; i < rows; i++){ free(used_for_row[i]); } free(used_for_row); return result; } |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 | #include <stdio.h> #include <stdlib.h> #include <assert.h> #define PH 16 // rref: Given a rows x cols matrix with modulo arithmetic modulo PH, // perform a reduction algorithm (as in the Python code) and return an // array used_for_row such that used_for_row[i] is a sorted list (ascending) // of the indices (from 0 to rows-1) that were “used” for row i. // // The parameter graphlen is used to decide which assertions and modifications // are performed on the pivot. int** rref(int** matrix, int rows, int cols, int graphlen) { int i, j; int extra = 0; int col = 0; // Allocate a 2D “boolean” array to keep track of the used rows. // Each used_for_row[i] is an integer array of length 'rows', holding 0/1. int **used_for_row = malloc(rows * sizeof(int*)); if (!used_for_row) exit(EXIT_FAILURE); for(i = 0; i < rows; i++){ used_for_row[i] = calloc(rows, sizeof(int)); if (!used_for_row[i]) exit(EXIT_FAILURE); used_for_row[i][i] = 1; // Initially, each row just “uses itself” } // First, reduce every entry modulo PH. for(i = 0; i < rows; i++){ for(j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } // Main loop. (In Python: while col+extra < matrix.shape[1]-1 and col < matrix.shape[0]) while ((col + extra) < (cols - 1) && col < rows) { // If the pivot candidate is 0 if(matrix[col][col + extra] == 0) { // Check if entire column (at index col) is 0. int allZero = 1; for(i = 0; i < rows; i++){ if(matrix[i][col] != 0) { allZero = 0; break; } } if(allZero) { extra++; continue; // skip the rest of the loop } // Look for another row in which the (col+extra)-th entry is nonzero. int other = -1; for(i = 0; i < rows; i++){ if(matrix[i][col+extra] != 0) other = i; // take the last such row found } if(other < col) { extra++; continue; } // Swap row 'col' with row 'other' in both matrix and used_for_row. { int *temp_row = matrix[col]; matrix[col] = matrix[other]; matrix[other] = temp_row; int *temp_used = used_for_row[col]; used_for_row[col] = used_for_row[other]; used_for_row[other] = temp_used; } } // Here we have a nonzero pivot in matrix[col][col+extra]. int pivot = matrix[col][col+extra]; if ((col + extra) < graphlen) { // The python code asserts: abs(pivot)==1 or abs(pivot)==PH-1. if (!((abs(pivot) == 1) || (abs(pivot) == PH - 1))) { // For production code you may wish to handle this error. assert(0 && "Pivot value is not ±1 mod PH in the top block"); } } else { // For (col+extra) >= graphlen, we expect abs(pivot)==2 or PH-2. if (!((abs(pivot) == 2) || (abs(pivot) == PH - 2))) { assert(0 && "Pivot value is not ±2 mod PH in the bottom block"); } // Adjust the pivot as in the Python code. pivot = pivot / 2; } // Multiply row 'col' by pivot so that pivot becomes 1 modulo PH. for(j = 0; j < cols; j++){ matrix[col][j] = (matrix[col][j] * pivot) % PH; if(matrix[col][j] < 0) matrix[col][j] += PH; } // For every other row that has a nonzero entry in column (col+extra), // eliminate that entry. for(i = 0; i < rows; i++){ if(i == col) continue; if(matrix[i][col+extra] != 0){ // Union: update used_for_row[i] = used_for_row[i] ∪ used_for_row[col] for(j = 0; j < rows; j++){ if(used_for_row[col][j]) used_for_row[i][j] = 1; } if(col < graphlen) { // Operation: matrix[i] -= matrix[col] * (matrix[i][col+extra]) int factor = matrix[i][col+extra]; for(j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - matrix[col][j] * factor) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } else { // Operation: while (matrix[i][col+extra] != 0) while(matrix[i][col+extra] != 0){ for(j = 0; j < cols; j++){ matrix[i][j] = (matrix[i][j] - matrix[col][j]) % PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } // Ensure row i is in the proper modulo range. for(j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } } col++; } // Final reduction: ensure every entry is in range [0, PH-1]. for(i = 0; i < rows; i++){ for(j = 0; j < cols; j++){ matrix[i][j] %= PH; if(matrix[i][j] < 0) matrix[i][j] += PH; } } // Now we convert the used_for_row boolean arrays into sorted lists. // For each row, count how many indices are present, allocate an int array, // and fill it with indices in increasing order. int **result = malloc(rows * sizeof(int*)); if (!result) exit(EXIT_FAILURE); for(i = 0; i < rows; i++){ int count = 0; for(j = 0; j < rows; j++){ if(used_for_row[i][j]) count++; } // Allocate an array for the indices. result[i] = malloc(count * sizeof(int)); if(!result[i]) exit(EXIT_FAILURE); int idx = 0; for(j = 0; j < rows; j++){ if(used_for_row[i][j]){ result[i][idx++] = j; } } // Because we examined indices from 0 to rows-1, they are already in increasing order. } // Free the temporary used_for_row boolean arrays. for(i = 0; i < rows; i++){ free(used_for_row[i]); } free(used_for_row); return result; } #include<stdio.h> #include<stdlib.h> int main() { int arr0[] = {1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}; int arr1[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr2[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -20}; int arr3[] = {0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, -20}; int arr4[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr5[] = {0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr6[] = {0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0}; int arr7[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, -30}; int arr8[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr9[] = {0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0, -20}; int arr10[] = {1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}; int arr11[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr12[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr13[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -14}; int arr14[] = {0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr15[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, -30}; int arr16[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr17[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr18[] = {0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr19[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13}; int arr20[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr21[] = {0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr22[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, -20}; int arr23[] = {0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10}; int arr24[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr25[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13}; int arr26[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr27[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13}; int arr28[] = {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr29[] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr30[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int arr31[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr32[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, -10}; int arr33[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13}; int arr34[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -11}; int arr35[] = {0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -9}; int arr36[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, -20}; int arr37[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, -40}; int arr38[] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int* arr[] = {arr0, arr1, arr2, arr3, arr4, arr5, arr6, arr7, arr8, arr9, arr10, arr11, arr12, arr13, arr14, arr15, arr16, arr17, arr18, arr19, arr20, arr21, arr22, arr23, arr24, arr25, arr26, arr27, arr28, arr29, arr30, arr31, arr32, arr33, arr34, arr35, arr36, arr37, arr38}; int** got = rref(arr, 39, 49, 37); int answer = got[3][0]+got[3][1]+got[3][2]+got[3][3]+got[3][4]+got[3][5]+got[3][6]; int expected = 146; if (answer != expected) { printf("Wrong answer; got %d instead of %d.\n", answer, expected); exit(1); } printf("All tests passed\n"); } |
All tests passed
Testing if the previous output contains the string All tests passed: True