permutation: Generate permutations of arrays
[ccan] / 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 }