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]
Okay, here is the C implementation of the `rref` function. **Assumptions:** 1. The input `matrix` is a dynamically allocated 2D array (`int**`) where `matrix[i]` points to a dynamically allocated array of `cols` integers. 2. The caller is responsible for freeing the memory allocated for the returned `int**` array (both the inner arrays and the outer array). 3. The value `PH = 16` is used as in the Python code. 4. The returned `int** used_for_row` will have `rows` inner arrays. Each inner array `used_for_row[i]` will contain the sorted indices of the original rows that contribute to the final row `i`, terminated by a `-1` sentinel value.
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 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 | #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> // For assertions (optional, can be removed) #define PH 16 // Helper function for correct modulo arithmetic (handles negative results) int mod(int a, int m) { return (a % m + m) % m; } // Helper function to swap two integer pointers (used for rows) void swap_int_ptr(int** a, int** b) { int* temp = *a; *a = *b; *b = temp; } // Helper function to swap two boolean pointers (used for tracking arrays) void swap_bool_ptr(bool** a, bool** b) { bool* temp = *a; *a = *b; *b = temp; } // Comparison function for qsort int compare_ints(const void* a, const void* b) { return (*(int*)a - *(int*)b); } /** * @brief Computes the Reduced Row Echelon Form (RREF) of a matrix modulo PH * and tracks the original rows contributing to each final row. * The input matrix is modified in place. * * @param matrix The input matrix (rows x cols). Modified in place. * @param rows Number of rows in the matrix. * @param cols Number of columns in the matrix. * @param graphlen Parameter influencing normalization/elimination strategy. * @return int** An array of arrays. result[i] contains the sorted indices * of original rows contributing to final row i, terminated by -1. * Returns NULL on allocation failure. Caller must free the result. */ int** rref(int** matrix, int rows, int cols, int graphlen) { if (!matrix || rows <= 0 || cols <= 0) { return NULL; // Invalid input } int extra = 0; int col = 0; // Represents the current row index we are trying to find a pivot for // --- Initialization of used_for_row tracking --- // Use boolean arrays for efficient union operations bool** temp_used_for_row = (bool**)malloc(rows * sizeof(bool*)); if (!temp_used_for_row) { perror("Failed to allocate memory for temp_used_for_row pointers"); return NULL; } for (int i = 0; i < rows; ++i) { // calloc initializes memory to zero (false) temp_used_for_row[i] = (bool*)calloc(rows, sizeof(bool)); if (!temp_used_for_row[i]) { perror("Failed to allocate memory for temp_used_for_row inner array"); // Clean up previously allocated rows for (int j = 0; j < i; ++j) { free(temp_used_for_row[j]); } free(temp_used_for_row); return NULL; } temp_used_for_row[i][i] = true; // Row i initially depends only on original row i } // --- Initial Modulo Operation --- for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { matrix[r][c] = mod(matrix[r][c], PH); } } // --- Main RREF Loop --- // Loop while we have columns to process and rows to use as pivots while (col < rows && col + extra < cols) { int pivot_col = col + extra; // Current column being considered for pivot // --- Find Pivot Row --- if (mod(matrix[col][pivot_col], PH) == 0) { int other_row = -1; // Find the last row below 'col' with a non-zero entry in pivot_col for (int r = rows - 1; r > col; --r) { if (mod(matrix[r][pivot_col], PH) != 0) { other_row = r; break; } } if (other_row == -1) { // All entries below (and at) matrix[col][pivot_col] are zero. // Check if the entire column is zero (Python used np.all) bool all_zero = true; for(int r = 0; r < rows; ++r) { // Check *entire* column if (mod(matrix[r][pivot_col], PH) != 0) { all_zero = false; // Python code found the *last* non-zero row. If it was < col, it skipped. // Let's replicate that specific check. int last_nonzero = -1; for(int r_check = rows - 1; r_check >= 0; --r_check) { if (mod(matrix[r_check][pivot_col], PH) != 0) { last_nonzero = r_check; break; } } if (last_nonzero < col) { all_zero = true; // Treat as if all zero for pivot purposes here } else { // This case implies a non-zero element exists >= col, // but matrix[col][pivot_col] was 0 and the loop above // didn't find one > col. This means the non-zero must be at 'col'. // This state shouldn't be reached if logic is sound, but handle defensively. // The original code would have skipped the column if other < col. // If other_row == -1 here, it means non-zeros only exist <= col. // If matrix[col][pivot_col] is 0, and non-zeros only exist < col, skip. bool non_zero_above = false; for(int r_check = 0; r_check < col; ++r_check) { if (mod(matrix[r_check][pivot_col], PH) != 0) { non_zero_above = true; break; } } if (non_zero_above) { all_zero = true; // Skip column if only non-zeros are above } else { // This implies matrix[col][pivot_col] must be the only non-zero >= col // but we are in the block where it's 0. Contradiction? // Let's trust the initial check and skip if other_row == -1. all_zero = true; } } break; // Exit the outer check loop } } if (all_zero) { extra++; // Skip this column continue; // Go to the next iteration of the while loop } // If we reach here, it means other_row must have been found > col, // but the initial check matrix[col][pivot_col] == 0 failed? // Let's re-check the logic flow. The Python code finds the *last* non-zero row `other`. // If `other < col`, it skips. If `other >= col` and `matrix[col][pivot_col] == 0`, it swaps `col` and `other`. // Let's re-implement the search for `other` more directly. other_row = -1; // Reset for (int r = rows - 1; r >= 0; --r) { // Find last non-zero in column if (mod(matrix[r][pivot_col], PH) != 0) { other_row = r; break; } } if (other_row == -1 || other_row < col) { // No suitable pivot found in this column extra++; continue; } // else: other_row >= col. Since matrix[col][pivot_col] is 0, other_row must be > col. // Swap row 'col' and 'other_row' swap_int_ptr(&matrix[col], &matrix[other_row]); swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]); } else { // Found a suitable row 'other_row' > col // Swap row 'col' and 'other_row' swap_int_ptr(&matrix[col], &matrix[other_row]); swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]); } } // Now, matrix[col][pivot_col] is guaranteed to be non-zero (mod PH) // --- Pivot Normalization --- int pivot_val = mod(matrix[col][pivot_col], PH); int multiplier = 1; // Default multiplier if (pivot_col < graphlen) { // Assert equivalent: Check if pivot is 1 or -1 (mod PH) // assert(pivot_val == 1 || pivot_val == PH - 1); if (pivot_val != 1 && pivot_val != PH - 1) { fprintf(stderr, "Assertion failed: pivot_val (%d) not 1 or %d at row %d, col %d (graphlen part)\n", pivot_val, PH-1, col, pivot_col); // Handle error appropriately, maybe return NULL after cleanup? // For now, proceed using pivot_val as multiplier. } multiplier = pivot_val; // Multiply row by pivot to make pivot element 1 (since 1*1=1, -1*-1=1 mod PH) } else { // Assert equivalent: Check if pivot is 2 or -2 (mod PH) // assert(pivot_val == 2 || pivot_val == PH - 2); if (pivot_val != 2 && pivot_val != PH - 2) { fprintf(stderr, "Assertion failed: pivot_val (%d) not 2 or %d at row %d, col %d (non-graphlen part)\n", pivot_val, PH-2, col, pivot_col); // Handle error appropriately } // Python code: pivot //= 2; matrix[col] *= pivot // If pivot_val = 2, pivot //= 2 gives 1. Row *= 1. Pivot element becomes 2*1 = 2. // If pivot_val = 14 (PH-2), pivot //= 2 gives 7. Row *= 7. Pivot element becomes 14*7 = 98 = 2 (mod 16). // So, the goal is to make the pivot element 2 (mod PH). // We need to find multiplier such that pivot_val * multiplier = 2 (mod PH) // This isn't generally possible. // Let's follow the Python code's effect: multiply by (pivot_val // 2) multiplier = (pivot_val == 2) ? 1 : 7; // Integer division equivalent for 2 and 14 } // Apply multiplier to the pivot row for (int c = 0; c < cols; ++c) { matrix[col][c] = mod(matrix[col][c] * multiplier, PH); } // After this step: // if pivot_col < graphlen, matrix[col][pivot_col] is 1 (mod PH) // if pivot_col >= graphlen, matrix[col][pivot_col] is 2 (mod PH) // --- Elimination --- for (int i = 0; i < rows; ++i) { if (i == col) continue; // Skip pivot row itself int factor = mod(matrix[i][pivot_col], PH); if (factor == 0) continue; // Already zero in this column // Update used_for_row[i] = used_for_row[i] | used_for_row[col] for (int k = 0; k < rows; ++k) { if (temp_used_for_row[col][k]) { temp_used_for_row[i][k] = true; } } // Perform elimination based on pivot column index if (pivot_col < graphlen) { // Standard Gaussian elimination: R_i = R_i - factor * R_col // Since matrix[col][pivot_col] is 1 (mod PH), we multiply R_col by 'factor' for (int c = 0; c < cols; ++c) { matrix[i][c] = mod(matrix[i][c] - factor * matrix[col][c], PH); } } else { // Special elimination: R_i = R_i - R_col (repeatedly) // Since matrix[col][pivot_col] is 2 (mod PH) // This only works correctly if the underlying field is effectively GF(2) // or if all 'factor' values are multiples of 2. // Replicating the Python 'while' loop: while (mod(matrix[i][pivot_col], PH) != 0) { for (int c = 0; c < cols; ++c) { matrix[i][c] = mod(matrix[i][c] - matrix[col][c], PH); } } } // Ensure row i is reduced mod PH (redundant if mod() used correctly inside, but safe) // for (int c = 0; c < cols; ++c) { // matrix[i][c] = mod(matrix[i][c], PH); // } } col++; // Move to the next row/pivot } // End while loop // --- Construct the final result from temp_used_for_row --- int** result = (int**)malloc(rows * sizeof(int*)); if (!result) { perror("Failed to allocate memory for result pointers"); // Clean up temp_used_for_row for (int i = 0; i < rows; ++i) free(temp_used_for_row[i]); free(temp_used_for_row); return NULL; } for (int i = 0; i < rows; ++i) { int count = 0; for (int k = 0; k < rows; ++k) { if (temp_used_for_row[i][k]) { count++; } } // Allocate space for indices + 1 for the -1 sentinel result[i] = (int*)malloc((count + 1) * sizeof(int)); if (!result[i]) { perror("Failed to allocate memory for result inner array"); // Clean up previously allocated result rows and temp_used_for_row for (int j = 0; j < i; ++j) free(result[j]); free(result); for (int k = 0; k < rows; ++k) free(temp_used_for_row[k]); free(temp_used_for_row); return NULL; } // Fill the result array with indices int current_idx = 0; for (int k = 0; k < rows; ++k) { if (temp_used_for_row[i][k]) { result[i][current_idx++] = k; } } result[i][current_idx] = -1; // Add sentinel // Sort the indices (as Python code returned sorted lists) qsort(result[i], count, sizeof(int), compare_ints); // Free the temporary boolean array for this row free(temp_used_for_row[i]); } // Free the outer temporary array free(temp_used_for_row); return result; } // --- Example Usage (Optional) --- void print_matrix(int** matrix, int rows, int cols) { printf("Matrix (%dx%d):\n", rows, cols); for (int i = 0; i < rows; ++i) { printf(" ["); for (int j = 0; j < cols; ++j) { printf("%3d", matrix[i][j]); } printf(" ]\n"); } } void print_used_for_row(int** used_rows, int rows) { printf("Used For Row:\n"); for (int i = 0; i < rows; ++i) { printf(" Row %d: [", i); int* current = used_rows[i]; while (*current != -1) { printf("%d", *current); current++; if (*current != -1) { printf(", "); } } printf("]\n"); } } void free_matrix(int** matrix, int rows) { if (!matrix) return; for (int i = 0; i < rows; ++i) { free(matrix[i]); } free(matrix); } void free_used_for_row(int** used_rows, int rows) { // Same implementation as free_matrix, just different name for clarity if (!used_rows) return; for (int i = 0; i < rows; ++i) { free(used_rows[i]); } free(used_rows); } int main() { // Example matching the logic (adjust values as needed) int rows = 4, cols = 5, graphlen = 2; // Allocate matrix int** matrix = (int**)malloc(rows * sizeof(int*)); for (int i = 0; i < rows; ++i) { matrix[i] = (int*)malloc(cols * sizeof(int)); } // Initialize matrix (example data) // [[1, 0, 1, 2, 5], // [0, 1, 1, 14, 3], // [0, 0, 0, 2, 8], // [1, 1, 0, 0, 9]] matrix[0][0] = 1; matrix[0][1] = 0; matrix[0][2] = 1; matrix[0][3] = 2; matrix[0][4] = 5; matrix[1][0] = 0; matrix[1][1] = 1; matrix[1][2] = 1; matrix[1][3] = 14; matrix[1][4] = 3; matrix[2][0] = 0; matrix[2][1] = 0; matrix[2][2] = 0; matrix[2][3] = 2; matrix[2][4] = 8; matrix[3][0] = 1; matrix[3][1] = 1; matrix[3][2] = 0; matrix[3][3] = 0; matrix[3][4] = 9; printf("Original Matrix:\n"); print_matrix(matrix, rows, cols); printf("Graphlen: %d, PH: %d\n\n", graphlen, PH); int** used_rows = rref(matrix, rows, cols, graphlen); if (used_rows) { printf("Matrix after RREF (mod %d):\n", PH); print_matrix(matrix, rows, cols); printf("\n"); print_used_for_row(used_rows, rows); // Free allocated memory free_used_for_row(used_rows, rows); } else { printf("RREF function failed (likely memory allocation error).\n"); } free_matrix(matrix, rows); // Free the matrix itself return 0; } |
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 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 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 | #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> // For assertions (optional, can be removed) #define PH 16 // Helper function for correct modulo arithmetic (handles negative results) int mod(int a, int m) { return (a % m + m) % m; } // Helper function to swap two integer pointers (used for rows) void swap_int_ptr(int** a, int** b) { int* temp = *a; *a = *b; *b = temp; } // Helper function to swap two boolean pointers (used for tracking arrays) void swap_bool_ptr(bool** a, bool** b) { bool* temp = *a; *a = *b; *b = temp; } // Comparison function for qsort int compare_ints(const void* a, const void* b) { return (*(int*)a - *(int*)b); } /** * @brief Computes the Reduced Row Echelon Form (RREF) of a matrix modulo PH * and tracks the original rows contributing to each final row. * The input matrix is modified in place. * * @param matrix The input matrix (rows x cols). Modified in place. * @param rows Number of rows in the matrix. * @param cols Number of columns in the matrix. * @param graphlen Parameter influencing normalization/elimination strategy. * @return int** An array of arrays. result[i] contains the sorted indices * of original rows contributing to final row i, terminated by -1. * Returns NULL on allocation failure. Caller must free the result. */ int** rref(int** matrix, int rows, int cols, int graphlen) { if (!matrix || rows <= 0 || cols <= 0) { return NULL; // Invalid input } int extra = 0; int col = 0; // Represents the current row index we are trying to find a pivot for // --- Initialization of used_for_row tracking --- // Use boolean arrays for efficient union operations bool** temp_used_for_row = (bool**)malloc(rows * sizeof(bool*)); if (!temp_used_for_row) { perror("Failed to allocate memory for temp_used_for_row pointers"); return NULL; } for (int i = 0; i < rows; ++i) { // calloc initializes memory to zero (false) temp_used_for_row[i] = (bool*)calloc(rows, sizeof(bool)); if (!temp_used_for_row[i]) { perror("Failed to allocate memory for temp_used_for_row inner array"); // Clean up previously allocated rows for (int j = 0; j < i; ++j) { free(temp_used_for_row[j]); } free(temp_used_for_row); return NULL; } temp_used_for_row[i][i] = true; // Row i initially depends only on original row i } // --- Initial Modulo Operation --- for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { matrix[r][c] = mod(matrix[r][c], PH); } } // --- Main RREF Loop --- // Loop while we have columns to process and rows to use as pivots while (col < rows && col + extra < cols) { int pivot_col = col + extra; // Current column being considered for pivot // --- Find Pivot Row --- if (mod(matrix[col][pivot_col], PH) == 0) { int other_row = -1; // Find the last row below 'col' with a non-zero entry in pivot_col for (int r = rows - 1; r > col; --r) { if (mod(matrix[r][pivot_col], PH) != 0) { other_row = r; break; } } if (other_row == -1) { // All entries below (and at) matrix[col][pivot_col] are zero. // Check if the entire column is zero (Python used np.all) bool all_zero = true; for(int r = 0; r < rows; ++r) { // Check *entire* column if (mod(matrix[r][pivot_col], PH) != 0) { all_zero = false; // Python code found the *last* non-zero row. If it was < col, it skipped. // Let's replicate that specific check. int last_nonzero = -1; for(int r_check = rows - 1; r_check >= 0; --r_check) { if (mod(matrix[r_check][pivot_col], PH) != 0) { last_nonzero = r_check; break; } } if (last_nonzero < col) { all_zero = true; // Treat as if all zero for pivot purposes here } else { // This case implies a non-zero element exists >= col, // but matrix[col][pivot_col] was 0 and the loop above // didn't find one > col. This means the non-zero must be at 'col'. // This state shouldn't be reached if logic is sound, but handle defensively. // The original code would have skipped the column if other < col. // If other_row == -1 here, it means non-zeros only exist <= col. // If matrix[col][pivot_col] is 0, and non-zeros only exist < col, skip. bool non_zero_above = false; for(int r_check = 0; r_check < col; ++r_check) { if (mod(matrix[r_check][pivot_col], PH) != 0) { non_zero_above = true; break; } } if (non_zero_above) { all_zero = true; // Skip column if only non-zeros are above } else { // This implies matrix[col][pivot_col] must be the only non-zero >= col // but we are in the block where it's 0. Contradiction? // Let's trust the initial check and skip if other_row == -1. all_zero = true; } } break; // Exit the outer check loop } } if (all_zero) { extra++; // Skip this column continue; // Go to the next iteration of the while loop } // If we reach here, it means other_row must have been found > col, // but the initial check matrix[col][pivot_col] == 0 failed? // Let's re-check the logic flow. The Python code finds the *last* non-zero row `other`. // If `other < col`, it skips. If `other >= col` and `matrix[col][pivot_col] == 0`, it swaps `col` and `other`. // Let's re-implement the search for `other` more directly. other_row = -1; // Reset for (int r = rows - 1; r >= 0; --r) { // Find last non-zero in column if (mod(matrix[r][pivot_col], PH) != 0) { other_row = r; break; } } if (other_row == -1 || other_row < col) { // No suitable pivot found in this column extra++; continue; } // else: other_row >= col. Since matrix[col][pivot_col] is 0, other_row must be > col. // Swap row 'col' and 'other_row' swap_int_ptr(&matrix[col], &matrix[other_row]); swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]); } else { // Found a suitable row 'other_row' > col // Swap row 'col' and 'other_row' swap_int_ptr(&matrix[col], &matrix[other_row]); swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]); } } // Now, matrix[col][pivot_col] is guaranteed to be non-zero (mod PH) // --- Pivot Normalization --- int pivot_val = mod(matrix[col][pivot_col], PH); int multiplier = 1; // Default multiplier if (pivot_col < graphlen) { // Assert equivalent: Check if pivot is 1 or -1 (mod PH) // assert(pivot_val == 1 || pivot_val == PH - 1); if (pivot_val != 1 && pivot_val != PH - 1) { fprintf(stderr, "Assertion failed: pivot_val (%d) not 1 or %d at row %d, col %d (graphlen part)\n", pivot_val, PH-1, col, pivot_col); // Handle error appropriately, maybe return NULL after cleanup? // For now, proceed using pivot_val as multiplier. } multiplier = pivot_val; // Multiply row by pivot to make pivot element 1 (since 1*1=1, -1*-1=1 mod PH) } else { // Assert equivalent: Check if pivot is 2 or -2 (mod PH) // assert(pivot_val == 2 || pivot_val == PH - 2); if (pivot_val != 2 && pivot_val != PH - 2) { fprintf(stderr, "Assertion failed: pivot_val (%d) not 2 or %d at row %d, col %d (non-graphlen part)\n", pivot_val, PH-2, col, pivot_col); // Handle error appropriately } // Python code: pivot //= 2; matrix[col] *= pivot // If pivot_val = 2, pivot //= 2 gives 1. Row *= 1. Pivot element becomes 2*1 = 2. // If pivot_val = 14 (PH-2), pivot //= 2 gives 7. Row *= 7. Pivot element becomes 14*7 = 98 = 2 (mod 16). // So, the goal is to make the pivot element 2 (mod PH). // We need to find multiplier such that pivot_val * multiplier = 2 (mod PH) // This isn't generally possible. // Let's follow the Python code's effect: multiply by (pivot_val // 2) multiplier = (pivot_val == 2) ? 1 : 7; // Integer division equivalent for 2 and 14 } // Apply multiplier to the pivot row for (int c = 0; c < cols; ++c) { matrix[col][c] = mod(matrix[col][c] * multiplier, PH); } // After this step: // if pivot_col < graphlen, matrix[col][pivot_col] is 1 (mod PH) // if pivot_col >= graphlen, matrix[col][pivot_col] is 2 (mod PH) // --- Elimination --- for (int i = 0; i < rows; ++i) { if (i == col) continue; // Skip pivot row itself int factor = mod(matrix[i][pivot_col], PH); if (factor == 0) continue; // Already zero in this column // Update used_for_row[i] = used_for_row[i] | used_for_row[col] for (int k = 0; k < rows; ++k) { if (temp_used_for_row[col][k]) { temp_used_for_row[i][k] = true; } } // Perform elimination based on pivot column index if (pivot_col < graphlen) { // Standard Gaussian elimination: R_i = R_i - factor * R_col // Since matrix[col][pivot_col] is 1 (mod PH), we multiply R_col by 'factor' for (int c = 0; c < cols; ++c) { matrix[i][c] = mod(matrix[i][c] - factor * matrix[col][c], PH); } } else { // Special elimination: R_i = R_i - R_col (repeatedly) // Since matrix[col][pivot_col] is 2 (mod PH) // This only works correctly if the underlying field is effectively GF(2) // or if all 'factor' values are multiples of 2. // Replicating the Python 'while' loop: while (mod(matrix[i][pivot_col], PH) != 0) { for (int c = 0; c < cols; ++c) { matrix[i][c] = mod(matrix[i][c] - matrix[col][c], PH); } } } // Ensure row i is reduced mod PH (redundant if mod() used correctly inside, but safe) // for (int c = 0; c < cols; ++c) { // matrix[i][c] = mod(matrix[i][c], PH); // } } col++; // Move to the next row/pivot } // End while loop // --- Construct the final result from temp_used_for_row --- int** result = (int**)malloc(rows * sizeof(int*)); if (!result) { perror("Failed to allocate memory for result pointers"); // Clean up temp_used_for_row for (int i = 0; i < rows; ++i) free(temp_used_for_row[i]); free(temp_used_for_row); return NULL; } for (int i = 0; i < rows; ++i) { int count = 0; for (int k = 0; k < rows; ++k) { if (temp_used_for_row[i][k]) { count++; } } // Allocate space for indices + 1 for the -1 sentinel result[i] = (int*)malloc((count + 1) * sizeof(int)); if (!result[i]) { perror("Failed to allocate memory for result inner array"); // Clean up previously allocated result rows and temp_used_for_row for (int j = 0; j < i; ++j) free(result[j]); free(result); for (int k = 0; k < rows; ++k) free(temp_used_for_row[k]); free(temp_used_for_row); return NULL; } // Fill the result array with indices int current_idx = 0; for (int k = 0; k < rows; ++k) { if (temp_used_for_row[i][k]) { result[i][current_idx++] = k; } } result[i][current_idx] = -1; // Add sentinel // Sort the indices (as Python code returned sorted lists) qsort(result[i], count, sizeof(int), compare_ints); // Free the temporary boolean array for this row free(temp_used_for_row[i]); } // Free the outer temporary array free(temp_used_for_row); return result; } // --- Example Usage (Optional) --- void print_matrix(int** matrix, int rows, int cols) { printf("Matrix (%dx%d):\n", rows, cols); for (int i = 0; i < rows; ++i) { printf(" ["); for (int j = 0; j < cols; ++j) { printf("%3d", matrix[i][j]); } printf(" ]\n"); } } void print_used_for_row(int** used_rows, int rows) { printf("Used For Row:\n"); for (int i = 0; i < rows; ++i) { printf(" Row %d: [", i); int* current = used_rows[i]; while (*current != -1) { printf("%d", *current); current++; if (*current != -1) { printf(", "); } } printf("]\n"); } } void free_matrix(int** matrix, int rows) { if (!matrix) return; for (int i = 0; i < rows; ++i) { free(matrix[i]); } free(matrix); } void free_used_for_row(int** used_rows, int rows) { // Same implementation as free_matrix, just different name for clarity if (!used_rows) return; for (int i = 0; i < rows; ++i) { free(used_rows[i]); } free(used_rows); } int main() { // Example matching the logic (adjust values as needed) int rows = 4, cols = 5, graphlen = 2; // Allocate matrix int** matrix = (int**)malloc(rows * sizeof(int*)); for (int i = 0; i < rows; ++i) { matrix[i] = (int*)malloc(cols * sizeof(int)); } // Initialize matrix (example data) // [[1, 0, 1, 2, 5], // [0, 1, 1, 14, 3], // [0, 0, 0, 2, 8], // [1, 1, 0, 0, 9]] matrix[0][0] = 1; matrix[0][1] = 0; matrix[0][2] = 1; matrix[0][3] = 2; matrix[0][4] = 5; matrix[1][0] = 0; matrix[1][1] = 1; matrix[1][2] = 1; matrix[1][3] = 14; matrix[1][4] = 3; matrix[2][0] = 0; matrix[2][1] = 0; matrix[2][2] = 0; matrix[2][3] = 2; matrix[2][4] = 8; matrix[3][0] = 1; matrix[3][1] = 1; matrix[3][2] = 0; matrix[3][3] = 0; matrix[3][4] = 9; printf("Original Matrix:\n"); print_matrix(matrix, rows, cols); printf("Graphlen: %d, PH: %d\n\n", graphlen, PH); int** used_rows = rref(matrix, rows, cols, graphlen); if (used_rows) { printf("Matrix after RREF (mod %d):\n", PH); print_matrix(matrix, rows, cols); printf("\n"); print_used_for_row(used_rows, rows); // Free allocated memory free_used_for_row(used_rows, rows); } else { printf("RREF function failed (likely memory allocation error).\n"); } free_matrix(matrix, rows); // Free the matrix itself return 0; } |
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 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 | #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> // For assertions (optional, can be removed) #define PH 16 // Helper function for correct modulo arithmetic (handles negative results) int mod(int a, int m) { return (a % m + m) % m; } // Helper function to swap two integer pointers (used for rows) void swap_int_ptr(int** a, int** b) { int* temp = *a; *a = *b; *b = temp; } // Helper function to swap two boolean pointers (used for tracking arrays) void swap_bool_ptr(bool** a, bool** b) { bool* temp = *a; *a = *b; *b = temp; } // Comparison function for qsort int compare_ints(const void* a, const void* b) { return (*(int*)a - *(int*)b); } /** * @brief Computes the Reduced Row Echelon Form (RREF) of a matrix modulo PH * and tracks the original rows contributing to each final row. * The input matrix is modified in place. * * @param matrix The input matrix (rows x cols). Modified in place. * @param rows Number of rows in the matrix. * @param cols Number of columns in the matrix. * @param graphlen Parameter influencing normalization/elimination strategy. * @return int** An array of arrays. result[i] contains the sorted indices * of original rows contributing to final row i, terminated by -1. * Returns NULL on allocation failure. Caller must free the result. */ int** rref(int** matrix, int rows, int cols, int graphlen) { if (!matrix || rows <= 0 || cols <= 0) { return NULL; // Invalid input } int extra = 0; int col = 0; // Represents the current row index we are trying to find a pivot for // --- Initialization of used_for_row tracking --- // Use boolean arrays for efficient union operations bool** temp_used_for_row = (bool**)malloc(rows * sizeof(bool*)); if (!temp_used_for_row) { perror("Failed to allocate memory for temp_used_for_row pointers"); return NULL; } for (int i = 0; i < rows; ++i) { // calloc initializes memory to zero (false) temp_used_for_row[i] = (bool*)calloc(rows, sizeof(bool)); if (!temp_used_for_row[i]) { perror("Failed to allocate memory for temp_used_for_row inner array"); // Clean up previously allocated rows for (int j = 0; j < i; ++j) { free(temp_used_for_row[j]); } free(temp_used_for_row); return NULL; } temp_used_for_row[i][i] = true; // Row i initially depends only on original row i } // --- Initial Modulo Operation --- for (int r = 0; r < rows; ++r) { for (int c = 0; c < cols; ++c) { matrix[r][c] = mod(matrix[r][c], PH); } } // --- Main RREF Loop --- // Loop while we have columns to process and rows to use as pivots while (col < rows && col + extra < cols) { int pivot_col = col + extra; // Current column being considered for pivot // --- Find Pivot Row --- if (mod(matrix[col][pivot_col], PH) == 0) { int other_row = -1; // Find the last row below 'col' with a non-zero entry in pivot_col for (int r = rows - 1; r > col; --r) { if (mod(matrix[r][pivot_col], PH) != 0) { other_row = r; break; } } if (other_row == -1) { // All entries below (and at) matrix[col][pivot_col] are zero. // Check if the entire column is zero (Python used np.all) bool all_zero = true; for(int r = 0; r < rows; ++r) { // Check *entire* column if (mod(matrix[r][pivot_col], PH) != 0) { all_zero = false; // Python code found the *last* non-zero row. If it was < col, it skipped. // Let's replicate that specific check. int last_nonzero = -1; for(int r_check = rows - 1; r_check >= 0; --r_check) { if (mod(matrix[r_check][pivot_col], PH) != 0) { last_nonzero = r_check; break; } } if (last_nonzero < col) { all_zero = true; // Treat as if all zero for pivot purposes here } else { // This case implies a non-zero element exists >= col, // but matrix[col][pivot_col] was 0 and the loop above // didn't find one > col. This means the non-zero must be at 'col'. // This state shouldn't be reached if logic is sound, but handle defensively. // The original code would have skipped the column if other < col. // If other_row == -1 here, it means non-zeros only exist <= col. // If matrix[col][pivot_col] is 0, and non-zeros only exist < col, skip. bool non_zero_above = false; for(int r_check = 0; r_check < col; ++r_check) { if (mod(matrix[r_check][pivot_col], PH) != 0) { non_zero_above = true; break; } } if (non_zero_above) { all_zero = true; // Skip column if only non-zeros are above } else { // This implies matrix[col][pivot_col] must be the only non-zero >= col // but we are in the block where it's 0. Contradiction? // Let's trust the initial check and skip if other_row == -1. all_zero = true; } } break; // Exit the outer check loop } } if (all_zero) { extra++; // Skip this column continue; // Go to the next iteration of the while loop } // If we reach here, it means other_row must have been found > col, // but the initial check matrix[col][pivot_col] == 0 failed? // Let's re-check the logic flow. The Python code finds the *last* non-zero row `other`. // If `other < col`, it skips. If `other >= col` and `matrix[col][pivot_col] == 0`, it swaps `col` and `other`. // Let's re-implement the search for `other` more directly. other_row = -1; // Reset for (int r = rows - 1; r >= 0; --r) { // Find last non-zero in column if (mod(matrix[r][pivot_col], PH) != 0) { other_row = r; break; } } if (other_row == -1 || other_row < col) { // No suitable pivot found in this column extra++; continue; } // else: other_row >= col. Since matrix[col][pivot_col] is 0, other_row must be > col. // Swap row 'col' and 'other_row' swap_int_ptr(&matrix[col], &matrix[other_row]); swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]); } else { // Found a suitable row 'other_row' > col // Swap row 'col' and 'other_row' swap_int_ptr(&matrix[col], &matrix[other_row]); swap_bool_ptr(&temp_used_for_row[col], &temp_used_for_row[other_row]); } } // Now, matrix[col][pivot_col] is guaranteed to be non-zero (mod PH) // --- Pivot Normalization --- int pivot_val = mod(matrix[col][pivot_col], PH); int multiplier = 1; // Default multiplier if (pivot_col < graphlen) { // Assert equivalent: Check if pivot is 1 or -1 (mod PH) // assert(pivot_val == 1 || pivot_val == PH - 1); if (pivot_val != 1 && pivot_val != PH - 1) { fprintf(stderr, "Assertion failed: pivot_val (%d) not 1 or %d at row %d, col %d (graphlen part)\n", pivot_val, PH-1, col, pivot_col); // Handle error appropriately, maybe return NULL after cleanup? // For now, proceed using pivot_val as multiplier. } multiplier = pivot_val; // Multiply row by pivot to make pivot element 1 (since 1*1=1, -1*-1=1 mod PH) } else { // Assert equivalent: Check if pivot is 2 or -2 (mod PH) // assert(pivot_val == 2 || pivot_val == PH - 2); if (pivot_val != 2 && pivot_val != PH - 2) { fprintf(stderr, "Assertion failed: pivot_val (%d) not 2 or %d at row %d, col %d (non-graphlen part)\n", pivot_val, PH-2, col, pivot_col); // Handle error appropriately } // Python code: pivot //= 2; matrix[col] *= pivot // If pivot_val = 2, pivot //= 2 gives 1. Row *= 1. Pivot element becomes 2*1 = 2. // If pivot_val = 14 (PH-2), pivot //= 2 gives 7. Row *= 7. Pivot element becomes 14*7 = 98 = 2 (mod 16). // So, the goal is to make the pivot element 2 (mod PH). // We need to find multiplier such that pivot_val * multiplier = 2 (mod PH) // This isn't generally possible. // Let's follow the Python code's effect: multiply by (pivot_val // 2) multiplier = (pivot_val == 2) ? 1 : 7; // Integer division equivalent for 2 and 14 } // Apply multiplier to the pivot row for (int c = 0; c < cols; ++c) { matrix[col][c] = mod(matrix[col][c] * multiplier, PH); } // After this step: // if pivot_col < graphlen, matrix[col][pivot_col] is 1 (mod PH) // if pivot_col >= graphlen, matrix[col][pivot_col] is 2 (mod PH) // --- Elimination --- for (int i = 0; i < rows; ++i) { if (i == col) continue; // Skip pivot row itself int factor = mod(matrix[i][pivot_col], PH); if (factor == 0) continue; // Already zero in this column // Update used_for_row[i] = used_for_row[i] | used_for_row[col] for (int k = 0; k < rows; ++k) { if (temp_used_for_row[col][k]) { temp_used_for_row[i][k] = true; } } // Perform elimination based on pivot column index if (pivot_col < graphlen) { // Standard Gaussian elimination: R_i = R_i - factor * R_col // Since matrix[col][pivot_col] is 1 (mod PH), we multiply R_col by 'factor' for (int c = 0; c < cols; ++c) { matrix[i][c] = mod(matrix[i][c] - factor * matrix[col][c], PH); } } else { // Special elimination: R_i = R_i - R_col (repeatedly) // Since matrix[col][pivot_col] is 2 (mod PH) // This only works correctly if the underlying field is effectively GF(2) // or if all 'factor' values are multiples of 2. // Replicating the Python 'while' loop: while (mod(matrix[i][pivot_col], PH) != 0) { for (int c = 0; c < cols; ++c) { matrix[i][c] = mod(matrix[i][c] - matrix[col][c], PH); } } } // Ensure row i is reduced mod PH (redundant if mod() used correctly inside, but safe) // for (int c = 0; c < cols; ++c) { // matrix[i][c] = mod(matrix[i][c], PH); // } } col++; // Move to the next row/pivot } // End while loop // --- Construct the final result from temp_used_for_row --- int** result = (int**)malloc(rows * sizeof(int*)); if (!result) { perror("Failed to allocate memory for result pointers"); // Clean up temp_used_for_row for (int i = 0; i < rows; ++i) free(temp_used_for_row[i]); free(temp_used_for_row); return NULL; } for (int i = 0; i < rows; ++i) { int count = 0; for (int k = 0; k < rows; ++k) { if (temp_used_for_row[i][k]) { count++; } } // Allocate space for indices + 1 for the -1 sentinel result[i] = (int*)malloc((count + 1) * sizeof(int)); if (!result[i]) { perror("Failed to allocate memory for result inner array"); // Clean up previously allocated result rows and temp_used_for_row for (int j = 0; j < i; ++j) free(result[j]); free(result); for (int k = 0; k < rows; ++k) free(temp_used_for_row[k]); free(temp_used_for_row); return NULL; } // Fill the result array with indices int current_idx = 0; for (int k = 0; k < rows; ++k) { if (temp_used_for_row[i][k]) { result[i][current_idx++] = k; } } result[i][current_idx] = -1; // Add sentinel // Sort the indices (as Python code returned sorted lists) qsort(result[i], count, sizeof(int), compare_ints); // Free the temporary boolean array for this row free(temp_used_for_row[i]); } // Free the outer temporary array free(temp_used_for_row); return result; } // --- Example Usage (Optional) --- void print_matrix(int** matrix, int rows, int cols) { printf("Matrix (%dx%d):\n", rows, cols); for (int i = 0; i < rows; ++i) { printf(" ["); for (int j = 0; j < cols; ++j) { printf("%3d", matrix[i][j]); } printf(" ]\n"); } } void print_used_for_row(int** used_rows, int rows) { printf("Used For Row:\n"); for (int i = 0; i < rows; ++i) { printf(" Row %d: [", i); int* current = used_rows[i]; while (*current != -1) { printf("%d", *current); current++; if (*current != -1) { printf(", "); } } printf("]\n"); } } void free_matrix(int** matrix, int rows) { if (!matrix) return; for (int i = 0; i < rows; ++i) { free(matrix[i]); } free(matrix); } void free_used_for_row(int** used_rows, int rows) { // Same implementation as free_matrix, just different name for clarity if (!used_rows) return; for (int i = 0; i < rows; ++i) { free(used_rows[i]); } free(used_rows); } int __delete_this__main() { // Example matching the logic (adjust values as needed) int rows = 4, cols = 5, graphlen = 2; // Allocate matrix int** matrix = (int**)malloc(rows * sizeof(int*)); for (int i = 0; i < rows; ++i) { matrix[i] = (int*)malloc(cols * sizeof(int)); } // Initialize matrix (example data) // [[1, 0, 1, 2, 5], // [0, 1, 1, 14, 3], // [0, 0, 0, 2, 8], // [1, 1, 0, 0, 9]] matrix[0][0] = 1; matrix[0][1] = 0; matrix[0][2] = 1; matrix[0][3] = 2; matrix[0][4] = 5; matrix[1][0] = 0; matrix[1][1] = 1; matrix[1][2] = 1; matrix[1][3] = 14; matrix[1][4] = 3; matrix[2][0] = 0; matrix[2][1] = 0; matrix[2][2] = 0; matrix[2][3] = 2; matrix[2][4] = 8; matrix[3][0] = 1; matrix[3][1] = 1; matrix[3][2] = 0; matrix[3][3] = 0; matrix[3][4] = 9; printf("Original Matrix:\n"); print_matrix(matrix, rows, cols); printf("Graphlen: %d, PH: %d\n\n", graphlen, PH); int** used_rows = rref(matrix, rows, cols, graphlen); if (used_rows) { printf("Matrix after RREF (mod %d):\n", PH); print_matrix(matrix, rows, cols); printf("\n"); print_used_for_row(used_rows, rows); // Free allocated memory free_used_for_row(used_rows, rows); } else { printf("RREF function failed (likely memory allocation error).\n"); } free_matrix(matrix, rows); // Free the matrix itself return 0; } #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