diff options
Diffstat (limited to 'src/utils/math.h')
| -rw-r--r-- | src/utils/math.h | 29 |
1 files changed, 4 insertions, 25 deletions
diff --git a/src/utils/math.h b/src/utils/math.h index 732a031..4b1da12 100644 --- a/src/utils/math.h +++ b/src/utils/math.h | |||
| @@ -3,7 +3,6 @@ | |||
| 3 | #define MAX(x, y) ((x) > (y) ? (x) : (y)) | 3 | #define MAX(x, y) ((x) > (y) ? (x) : (y)) |
| 4 | #define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) | 4 | #define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) |
| 5 | 5 | ||
| 6 | STATIC int64_t factorial(int64_t); | ||
| 7 | STATIC bool isperm(size_t, const uint8_t *); | 6 | STATIC bool isperm(size_t, const uint8_t *); |
| 8 | STATIC int64_t permtoindex(size_t, const uint8_t *); | 7 | STATIC int64_t permtoindex(size_t, const uint8_t *); |
| 9 | STATIC void indextoperm(int64_t, size_t, uint8_t *); | 8 | STATIC void indextoperm(int64_t, size_t, uint8_t *); |
| @@ -12,26 +11,6 @@ STATIC int64_t digitstosumzero(size_t, const uint8_t *, uint8_t); | |||
| 12 | STATIC void sumzerotodigits(int64_t, size_t, uint8_t, uint8_t *); | 11 | STATIC void sumzerotodigits(int64_t, size_t, uint8_t, uint8_t *); |
| 13 | STATIC double intpow(double, uint64_t); | 12 | STATIC double intpow(double, uint64_t); |
| 14 | 13 | ||
| 15 | STATIC int64_t | ||
| 16 | factorial(int64_t n) | ||
| 17 | { | ||
| 18 | int64_t i, ret; | ||
| 19 | |||
| 20 | if (n > FACTORIAL_MAX) { | ||
| 21 | LOG("Error: won't compute factorial for n=%" PRId64 " because" | ||
| 22 | " it is larger than %" PRId64 "\n", n, FACTORIAL_MAX); | ||
| 23 | return -1; | ||
| 24 | } | ||
| 25 | |||
| 26 | if (n < 0) | ||
| 27 | return 0; | ||
| 28 | |||
| 29 | for (i = 1, ret = 1; i <= n; i++) | ||
| 30 | ret *= i; | ||
| 31 | |||
| 32 | return ret; | ||
| 33 | } | ||
| 34 | |||
| 35 | STATIC bool | 14 | STATIC bool |
| 36 | isperm(size_t n, const uint8_t *a) | 15 | isperm(size_t n, const uint8_t *a) |
| 37 | { | 16 | { |
| @@ -78,7 +57,7 @@ permtoindex(size_t n, const uint8_t *a) | |||
| 78 | for (i = 0, ret = 0; i < n; i++) { | 57 | for (i = 0, ret = 0; i < n; i++) { |
| 79 | for (j = i+1, c = 0; j < n; j++) | 58 | for (j = i+1, c = 0; j < n; j++) |
| 80 | c += (a[i] > a[j]) ? 1 : 0; | 59 | c += (a[i] > a[j]) ? 1 : 0; |
| 81 | ret += factorial(n-i-1) * c; | 60 | ret += factorial[n-i-1] * c; |
| 82 | } | 61 | } |
| 83 | 62 | ||
| 84 | return ret; | 63 | return ret; |
| @@ -99,15 +78,15 @@ indextoperm(int64_t p, size_t n, uint8_t *r) | |||
| 99 | 78 | ||
| 100 | memset(a, 0, n); | 79 | memset(a, 0, n); |
| 101 | 80 | ||
| 102 | if (p < 0 || p >= factorial(n)) | 81 | if (p < 0 || p >= factorial[n]) |
| 103 | goto indextoperm_error; | 82 | goto indextoperm_error; |
| 104 | 83 | ||
| 105 | for (i = 0; i < n; i++) { | 84 | for (i = 0; i < n; i++) { |
| 106 | for (j = 0, c = 0; c <= p / factorial(n-i-1); j++) | 85 | for (j = 0, c = 0; c <= p / factorial[n-i-1]; j++) |
| 107 | c += a[j] ? 0 : 1; | 86 | c += a[j] ? 0 : 1; |
| 108 | r[i] = j-1; | 87 | r[i] = j-1; |
| 109 | a[j-1] = 1; | 88 | a[j-1] = 1; |
| 110 | p %= factorial(n-i-1); | 89 | p %= factorial[n-i-1]; |
| 111 | } | 90 | } |
| 112 | 91 | ||
| 113 | if (!isperm(n, r)) | 92 | if (!isperm(n, r)) |
