From 3568412f8f230774d0d11d7ed1c897424f95d3ef Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 11 Nov 2021 21:37:34 +0100 Subject: Rewritten from scratch. Welocme nissy 2.0! --- src/utils.c | 398 +++++++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 270 insertions(+), 128 deletions(-) (limited to 'src/utils.c') diff --git a/src/utils.c b/src/utils.c index 5b7df06..f72a00e 100644 --- a/src/utils.c +++ b/src/utils.c @@ -1,132 +1,274 @@ #include "utils.h" -/* Hardcoded factorial of small numbers (n<=12). */ -int factorial[13] = { - 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600 -}; - -/* swaps two integers */ -void swap(int *a, int *b) { - int aux = *a; - *a = *b; - *b = aux; -} - -/* Converts the integer a to its representation in base b (first n digits - * only) and saves the result in r. */ -void int_to_digit_array(int a, int b, int n, int *r) { - for (int i = 0; i < n; i++) { - r[i] = a % b; - a /= b; - } -} - -/* Converts the array of n digits a to a integer using base b. */ -int digit_array_to_int(int *a, int n, int b) { - int ret = 0, p = 1; - for (int i = 0; i < n; i++) { - ret += a[i] * p; - p *= b; - } - return ret; -} - -/* Converts a permutation on [0..(n-1)] into the integer i which is the index - * of the permutation in the sorted list of all n! such permutations. - * Only works for n<=12. */ -int perm_to_index(int *a, int n) { - int ret = 0; - for (int i = 0; i < n; i++) { - int c = 0; - for (int j = i+1; j < n; j++) - if (a[i] > a[j]) - c++; - ret += factorial[n-i-1] * c; - } - return ret; -} - -/* Converts a permutation index to the actual permutation as an array - * (see perm_to_index) and saves the result to r. */ -void index_to_perm(int p, int n, int *r) { - int a[n]; - for (int j = 0; j < n; j++) - a[j] = 0; /* picked elements */ - for (int i = 0; i < n; i++) { - int c = 0, j = 0; - while (c <= p / factorial[n-i-1]) { - if (!a[j]) - c++; - j++; - } - r[i] = j-1; - a[j-1] = 1; - p %= factorial[n-i-1]; - } -} - - -int perm_sign_array(int a[], int n) { - int ret = 0; - for (int i = 0; i < n; i++) - for (int j = i+1; j < n; j++) - if (a[i]>a[j]) - ret++; - return ret % 2; -} - -int perm_sign_int(int p, int n) { - int a[n]; - index_to_perm(p, n, a); - return perm_sign_array(a, n); -} - - -/* Converts a k-element subset of a set with an element from an array of n - * elements, of which k are 1 (or just non-zero) and n-k are 0, to its index - * in the sorted list of all such subsets. - * Works only for n <= 12. */ -int subset_to_index(int *a, int n, int k) { - int ret = 0; - for (int i = 0; i < n; i++) { - if (k == n-i) - return ret; - if (a[i]) { - ret += factorial[n-i-1] / (factorial[k] * factorial[n-i-1-k]); - k--; - } - } - return ret; -} - -/* Inverse of the above */ -void index_to_subset(int s, int n, int k, int *r) { - for (int i = 0; i < n; i++) { - if (k == n-i) { - for (int j = i; j < n; j++) - r[j] = 1; - return; - } - int v = factorial[n-i-1] / (factorial[k] * factorial[n-i-1-k]); - if (s >= v) { - r[i] = 1; - k--; - s -= v; - } else { - r[i] = 0; - } - } -} - -/* Converts the first n-1 digits of a number to an array a of digits in base b; - * then adds one element to the array, so that the sum of the elements of a is - * zero modulo b. - * This is used for determing the edge orientation from an 11-bits integer or - * the corner orientation from a 7-trits integer. */ -void int_to_sum_zero_array(int x, int b, int n, int *a) { - int_to_digit_array(x, b, n-1, a); - int s = 0; - for (int i = 0; i < n - 1; i++) s = (s + a[i]) % b; - a[n-1] = (b - s) % b; +void +apply_permutation(int *perm, int *set, int n) +{ + int *aux = malloc(n * sizeof(int)); + int i; + + if (!is_perm(perm, n)) + return; + + for (i = 0; i < n; i++) + aux[i] = set[perm[i]]; + + memcpy(set, aux, n * sizeof(int)); + free(aux); +} + +int +binomial(int n, int k) +{ + if (n < 0 || k < 0 || k > n) + return 0; + + return factorial(n) / (factorial(k) * factorial(n-k)); +} + +int +digit_array_to_int(int *a, int n, int b) +{ + int i, ret = 0, p = 1; + + for (i = 0; i < n; i++, p *= b) + ret += a[i] * p; + + return ret; +} + +int +factorial(int n) +{ + int i, ret = 1; + + if (n < 0) + return 0; + + for (i = 1; i <= n; i++) + ret *= i; + + return ret; +} + +void +index_to_perm(int p, int n, int *r) +{ + int *a = malloc(n * sizeof(int)); + int i, j, c; + + for (i = 0; i < n; i++) + a[i] = 0; + + if (p < 0 || p >= factorial(n)) + for (i = 0; i < n; i++) + r[i] = -1; + + for (i = 0; i < n; i++) { + c = 0; + j = 0; + while (c <= p / factorial(n-i-1)) + c += a[j++] ? 0 : 1; + r[i] = j-1; + a[j-1] = 1; + p %= factorial(n-i-1); + } + + free(a); +} + +void +index_to_subset(int s, int n, int k, int *r) +{ + int i, j, v; + + if (s < 0 || s >= binomial(n, k)) { + for (i = 0; i < n; i++) + r[i] = -1; + return; + } + + for (i = 0; i < n; i++) { + if (k == n-i) { + for (j = i; j < n; j++) + r[j] = 1; + return; + } + + if (k == 0) { + for (j = i; j < n; j++) + r[j] = 0; + return; + } + + v = binomial(n-i-1, k); + if (s >= v) { + r[i] = 1; + k--; + s -= v; + } else { + r[i] = 0; + } + } +} + +void +int_to_digit_array(int a, int b, int n, int *r) +{ + int i; + + if (b <= 1) + for (i = 0; i < n; i++) + r[i] = 0; + else + for (i = 0; i < n; i++, a /= b) + r[i] = a % b; +} + +void +int_to_sum_zero_array(int x, int b, int n, int *a) +{ + int i, s = 0; + + if (b <= 1) { + for (i = 0; i < n; i++) + a[i] = 0; + } else { + int_to_digit_array(x, b, n-1, a); + for (i = 0; i < n - 1; i++) + s = (s + a[i]) % b; + a[n-1] = (b - s) % b; + } +} + +int +invert_digits(int a, int b, int n) +{ + int i, ret, *r = malloc(n * sizeof(int)); + + int_to_digit_array(a, b, n, r); + for (i = 0; i < n; i++) + r[i] = (b-r[i]) % b; + + ret = digit_array_to_int(r, n, b); + free(r); + return ret; +} + +bool +is_perm(int *a, int n) +{ + int *aux = malloc(n * sizeof(int)); + int i; + + for (i = 0; i < n; i++) + if (a[i] < 0 || a[i] >= n) + return false; + else + aux[a[i]] = 1; + + for (i = 0; i < n; i++) + if (!aux[i]) + return false; + + free(aux); + + return true; +} + +bool +is_subset(int *a, int n, int k) +{ + int i, sum = 0; + + for (i = 0; i < n; i++) + sum += a[i] ? 1 : 0; + + return sum == k; +} + +int +perm_sign(int *a, int n) +{ + int i, j, ret = 0; + + if (!is_perm(a,n)) + return -1; + + for (i = 0; i < n; i++) + for (j = i+1; j < n; j++) + ret += (a[i] > a[j]) ? 1 : 0; + + return ret % 2; +} + +int +perm_to_index(int *a, int n) +{ + int i, j, c, ret = 0; + + if (!is_perm(a, n)) + return -1; + + for (i = 0; i < n; i++) { + c = 0; + for (j = i+1; j < n; j++) + c += (a[i] > a[j]) ? 1 : 0; + ret += factorial(n-i-1) * c; + } + + return ret; +} + +int +powint(int a, int b) +{ + if (b < 0) + return 0; + if (b == 0) + return 1; + + if (b % 2) + return a * powint(a, b-1); + else + return powint(a*a, b/2); +} + +int +subset_to_index(int *a, int n, int k) +{ + int i, ret = 0; + + if (!is_subset(a, n, k)) + return binomial(n, k); + + for (i = 0; i < n; i++) { + if (k == n-i) + return ret; + if (a[i]) { + ret += binomial(n-i-1, k); + k--; + } + } + + return ret; +} + +void +sum_arrays_mod(int *src, int *dst, int n, int m) +{ + int i; + + for (i = 0; i < n; i++) + dst[i] = (m <= 0) ? 0 : (src[i] + dst[i]) % m; +} + +void +swap(int *a, int *b) +{ + int aux; + + aux = *a; + *a = *b; + *b = aux; } -- cgit v1.3