permutation: Generate permutations of arrays

[ccan] / ccan / permutation / permutation.c

diff --git a/ccan/permutation/permutation.c b/ccan/permutation/permutation.c
new file mode 100644 (file)
index 0000000..19139d5
--- /dev/null
+++ b/ccan/permutation/permutation.c
@@ -0,0 +1,100 @@
+/* GNU LGPL version 2 (or later) - see LICENSE file for details */
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/build_assert/build_assert.h>
+#include <ccan/mem/mem.h>
+#include <ccan/permutation/permutation.h>
+
+unsigned long long permutation_count(int n)
+{
+       unsigned long long count = 1;
+       int i;
+
+       for (i = 1; i <=n; i++)
+               count *= i;
+
+       return count;
+}
+
+struct plain_change_state {
+       int8_t dir : 2;
+       uint8_t pos : PERMUTATION_MAX_SHIFT;
+};
+
+static inline struct plain_change_state *get_state(struct permutation *pi)
+{
+       BUILD_ASSERT(sizeof(struct plain_change_state) == 1);
+
+       return (struct plain_change_state *)(pi + 1) + pi->n;
+}
+
+struct permutation *permutation_new(int n)
+{
+       struct permutation *pi;
+       int i;
+       struct plain_change_state *xs;
+
+       assert(n <= PERMUTATION_MAX_ITEMS);
+
+       pi = malloc(sizeof(*pi) + 2 * n);
+       if (!pi)
+               return NULL;
+
+       pi->n = n;
+
+       xs = get_state(pi);
+
+       for (i = 0; i < pi->n; i++) {
+               pi->v[i] = i;
+               xs[i].pos = i;
+               xs[i].dir = (i == 0) ? 0 : -1;
+       }
+
+       return pi;
+}
+
+permutation_swap_t permutation_change(struct permutation *pi)
+{
+       int v, w, i;
+       int a, b, vdir;
+       struct plain_change_state *xs = get_state(pi);
+
+       if (!pi->n)
+               return 0;
+
+       for (v = pi->n - 1; v > 0; v--) {
+               if (xs[v].dir)
+                       break;
+       }
+
+       a = xs[v].pos;
+       vdir = xs[v].dir;
+       if (!vdir)
+               return 0;
+
+       b = a + vdir;
+       w = pi->v[b];
+
+       pi->v[a] = w;
+       pi->v[b] = v;
+       xs[v].pos = b;
+       xs[w].pos = a;
+
+       /* If we reach the end, or the next item is larger, set
+        * direction to 0 */
+       if ((b == 0) || (b == (pi->n-1))
+           || (pi->v[b + vdir] > v))
+               xs[v].dir = 0;
+
+       /* Reset direction on all elements greater than the chosen one */
+       for (i = v + 1; i < pi->n; i++) {
+               if (xs[i].pos < b)
+                       xs[i].dir = 1;
+               else
+                       xs[i].dir = -1;
+       }
+
+       return (b * PERMUTATION_MAX_ITEMS) + a;
+}