1 /* GNU LGPL version 2 (or later) - see LICENSE file for details */
6 #include <ccan/build_assert/build_assert.h>
7 #include <ccan/mem/mem.h>
8 #include <ccan/permutation/permutation.h>
10 unsigned long long permutation_count(int n)
12 unsigned long long count = 1;
15 for (i = 1; i <=n; i++)
21 struct plain_change_state {
23 uint8_t pos : PERMUTATION_MAX_SHIFT;
26 static inline struct plain_change_state *get_state(struct permutation *pi)
28 BUILD_ASSERT(sizeof(struct plain_change_state) == 1);
30 return (struct plain_change_state *)(pi + 1) + pi->n;
33 struct permutation *permutation_new(int n)
35 struct permutation *pi;
37 struct plain_change_state *xs;
39 assert(n <= PERMUTATION_MAX_ITEMS);
41 pi = malloc(sizeof(*pi) + 2 * n);
49 for (i = 0; i < pi->n; i++) {
52 xs[i].dir = (i == 0) ? 0 : -1;
58 permutation_swap_t permutation_change(struct permutation *pi)
62 struct plain_change_state *xs = get_state(pi);
67 for (v = pi->n - 1; v > 0; v--) {
85 /* If we reach the end, or the next item is larger, set
87 if ((b == 0) || (b == (pi->n-1))
88 || (pi->v[b + vdir] > v))
91 /* Reset direction on all elements greater than the chosen one */
92 for (i = v + 1; i < pi->n; i++) {
99 return (b * PERMUTATION_MAX_ITEMS) + a;