git.ozlabs.org Git - ccan/blob - ccan/permutation/permutation.c

   1 /* GNU LGPL version 2 (or later) - see LICENSE file for details */
   2 #include "config.h"
   3
   4 #include <assert.h>
   5
   6 #include <ccan/build_assert/build_assert.h>
   7 #include <ccan/mem/mem.h>
   8 #include <ccan/permutation/permutation.h>
   9
  10 unsigned long long permutation_count(int n)
  11 {
  12         unsigned long long count = 1;
  13         int i;
  14
  15         for (i = 1; i <=n; i++)
  16                 count *= i;
  17
  18         return count;
  19 }
  20
  21 struct plain_change_state {
  22         int8_t dir : 2;
  23         uint8_t pos : PERMUTATION_MAX_SHIFT;
  24 };
  25
  26 static inline struct plain_change_state *get_state(struct permutation *pi)
  27 {
  28         BUILD_ASSERT(sizeof(struct plain_change_state) == 1);
  29
  30         return (struct plain_change_state *)(pi + 1) + pi->n;
  31 }
  32
  33 struct permutation *permutation_new(int n)
  34 {
  35         struct permutation *pi;
  36         int i;
  37         struct plain_change_state *xs;
  38
  39         assert(n <= PERMUTATION_MAX_ITEMS);
  40
  41         pi = malloc(sizeof(*pi) + 2 * n);
  42         if (!pi)
  43                 return NULL;
  44
  45         pi->n = n;
  46
  47         xs = get_state(pi);
  48
  49         for (i = 0; i < pi->n; i++) {
  50                 pi->v[i] = i;
  51                 xs[i].pos = i;
  52                 xs[i].dir = (i == 0) ? 0 : -1;
  53         }
  54
  55         return pi;
  56 }
  57
  58 permutation_swap_t permutation_change(struct permutation *pi)
  59 {
  60         int v, w, i;
  61         int a, b, vdir;
  62         struct plain_change_state *xs = get_state(pi);
  63
  64         if (!pi->n)
  65                 return 0;
  66
  67         for (v = pi->n - 1; v > 0; v--) {
  68                 if (xs[v].dir)
  69                         break;
  70         }
  71
  72         a = xs[v].pos;
  73         vdir = xs[v].dir;
  74         if (!vdir)
  75                 return 0;
  76
  77         b = a + vdir;
  78         w = pi->v[b];
  79
  80         pi->v[a] = w;
  81         pi->v[b] = v;
  82         xs[v].pos = b;
  83         xs[w].pos = a;
  84
  85         /* If we reach the end, or the next item is larger, set
  86          * direction to 0 */
  87         if ((b == 0) || (b == (pi->n-1))
  88             || (pi->v[b + vdir] > v))
  89                 xs[v].dir = 0;
  90
  91         /* Reset direction on all elements greater than the chosen one */
  92         for (i = v + 1; i < pi->n; i++) {
  93                 if (xs[i].pos < b)
  94                         xs[i].dir = 1;
  95                 else
  96                         xs[i].dir = -1;
  97         }
  98
  99         return (b * PERMUTATION_MAX_ITEMS) + a;
 100 }