1 files changed, 294 insertions, 0 deletions

diff --git a/old/utils.c b/old/utils.c
new file mode 100644
index 0000000..3b5388e
--- /dev/null
+++ b/old/utils.c
@@ -0,0 +1,294 @@
+#include "utils.h"
+
+/* Generic utility functions *************************************************/
+
+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]];
+
+        intarrcopy(aux, set, n);
+        free(aux);
+}
+
+void
+intarrcopy(int *src, int *dst, int n)
+{
+        int i;
+        for (i = 0; i < n; i++)
+                dst[i] = src[i];
+}
+
+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
+sum(int *a, int n)
+{
+        int i, ret = 0;
+
+        for (i = 0; i < n; i++)
+                ret += a[i];
+        
+        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;
+}
+
+/* Standard mathematical functions *******************************************/
+
+int
+binomial(int n, int k)
+{
+        if (n < 0 || k < 0 || k > n)
+                return 0;
+
+        return factorial(n) / (factorial(k) * factorial(n-k));
+}
+
+int
+factorial(int n)
+{
+        int i, ret = 1;
+
+        if (n < 0)
+                return 0;
+
+        for (i = 1; i <= n; i++)
+                ret *= i;
+
+        return ret;
+}
+
+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
+powint(int a, int b)
+{
+        if (b < 0)
+                return 0; /* Truncate */
+        if (b == 0)
+                return 1;
+
+        if (b % 2)
+                return a * powint(a, b-1);
+        else
+                return powint(a*a, b/2);
+}
+
+/* Conversions to and from int (base b digits, permutations...) **************/
+
+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;
+}
+
+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, *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;
+
+        return digit_array_to_int(r, n, b);
+}
+
+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);
+}
+
+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;
+}
+
+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;
+                }
+        }
+}
+
+int subset_to_index(int *a, int n, int k) {
+        int i, ret = 0;
+
+        /* TODO: better checks */
+        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;
+}