#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/*
is_permutation: check whether two integer ranges are permutations.
Algorithm:
----------
1. If lengths differ → cannot be permutations.
2. Make local copies of both arrays (so we can sort them).
3. Sort both arrays using qsort (built-in C library).
4. Compare sorted arrays element-by-element.
5. If all elements match → they are permutations.
Complexity:
-----------
Sorting: O(n log n)
Comparison: O(n)
Total: O(n log n)
This is the most idiomatic and efficient approach in pure C
without external libraries.
*/
/* Comparison function for qsort */
static int cmp_int(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y); // idiomatic 3-way comparison
}
/* Check if two integer arrays are permutations */
bool is_permutation(const int *a, const int *b, size_t n) {
if (!a || !b) return false; // defensive programming
// Create local copies so we can sort safely
int *copy_a = malloc(n * sizeof(int));
int *copy_b = malloc(n * sizeof(int));
if (!copy_a || !copy_b) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
for (size_t i = 0; i < n; i++) {
copy_a[i] = a[i];
copy_b[i] = b[i];
}
// Sort both arrays
qsort(copy_a, n, sizeof(int), cmp_int);
qsort(copy_b, n, sizeof(int), cmp_int);
// Compare sorted arrays
bool equal = true;
for (size_t i = 0; i < n; i++) {
if (copy_a[i] != copy_b[i]) {
equal = false;
break;
}
}
free(copy_a);
free(copy_b);
return equal;
}
int main(void) {
int arr1[] = {3, 1, 2, 5, 4};
int arr2[] = {5, 4, 3, 2, 1};
int arr3[] = {1, 2, 3, 4, 6};
size_t n = sizeof(arr1) / sizeof(arr1[0]);
printf("arr1 vs arr2: %s\n", is_permutation(arr1, arr2, n) ? "PERMUTATION" : "NOT");
printf("arr1 vs arr3: %s\n", is_permutation(arr1, arr3, n) ? "PERMUTATION" : "NOT");
return 0;
}
/*
run:
arr1 vs arr2: PERMUTATION
arr1 vs arr3: NOT
*/
