permutation: Generate permutations of arrays
[ccan] / ccan / permutation / permutation.h
1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
2 #ifndef CCAN_PERMUTATION_H
3 #define CCAN_PERMUTATION_H
4
5 #include <config.h>
6
7 #include <stdlib.h>
8 #include <stdbool.h>
9 #include <stdint.h>
10 #include <assert.h>
11
12 #include <ccan/build_assert/build_assert.h>
13 #include <ccan/mem/mem.h>
14
15 /*
16  * We limit the number of elements to 64, to keep our data structures
17  * neat.  That seems low, but even 64! permutations is far too many to
18  * really generate in practice.
19  */
20 #define PERMUTATION_MAX_SHIFT   6
21 #define PERMUTATION_MAX_ITEMS   (1 << PERMUTATION_MAX_SHIFT)
22
23 /**
24  * struct permutation - represents a permutation
25  *
26  * The fields here are user visible, but it's allocated internally
27  * with extra state information appended.
28  *
29  * @n: Number of elements in the permutation
30  * @v: values 0..(n-1) arranged in current permutation
31  */
32 struct permutation {
33         int n;
34         uint8_t v[];
35         /* Private state data follows */
36 };
37
38
39 /**
40  * permutation_count - determine number of permutations
41  * @n: Number of elements
42  *
43  * Returns the number of permutations of @n elements.
44  */
45 unsigned long long permutation_count(int n);
46
47 /**
48  * permutation_swap_t - represents a swap of two items
49  *
50  * Encodes a swap of two elements in an array.  Should be treated as
51  * opaque, except that 0 always represents "swap nothing".
52  */
53 typedef unsigned permutation_swap_t;
54
55
56 /**
57  * permutation_swap_a - first item to swap
58  * permutation_swap_b - second item to swap
59  */
60 static inline int permutation_swap_a(permutation_swap_t swap)
61 {
62         return swap % PERMUTATION_MAX_ITEMS;
63 }
64
65 static inline int permutation_swap_b(permutation_swap_t swap)
66 {
67         return swap / PERMUTATION_MAX_ITEMS;
68 }
69
70 /**
71  * permutation_swap - swap two elements in an array
72  * @base: address of array
73  * @size: size of each array element
74  * @swap: which elements to swap
75  *
76  * Swaps the elements at index permutation_swap_a(@swap) and
77  * permutation_swap_b(@swap) in the array at @base of items of size
78  * @size.
79  */
80 static inline void permutation_swap_mem(void *base, size_t size,
81                                         permutation_swap_t swap)
82 {
83         char *ap = (char *)base + (permutation_swap_a(swap) * size);
84         char *bp = (char *)base + (permutation_swap_b(swap) * size);
85
86         BUILD_ASSERT(sizeof(permutation_swap_t) * 8
87                      >= PERMUTATION_MAX_SHIFT * 2);
88
89         if (!swap)
90                 return;
91
92         memswap(ap, bp, size);
93 }
94
95 /**
96  * PERMUTATION_SWAP - swap two elements in an array
97  * @a_: array
98  * @swap_: which elements to swap
99  *
100  * As permutation_swap(), but must act on a C array declared at the
101  * right size.
102  */
103 #define PERMUTATION_SWAP(a_, swap_)                                     \
104         do {                                                            \
105                 permutation_swap((a_), sizeof((a_)[0]), (swap_));       \
106         } while (0)
107
108
109 /**
110  * permutation_new - allocates a new identity permutation
111  * @n: Number of elements
112  *
113  * Allocates and initializes a new permutation of @n elements.
114  * Initially it represents the identity permutation.
115  */
116 struct permutation *permutation_new(int n);
117
118 /**
119  * PERMUTATION_NEW - allocates a new identity permutation of an array
120  * @array_: Array to permute
121  *
122  * As permutation_new() but take the number of elements from the
123  * declaration of @array_.
124  */
125 #define PERMUTATION_NEW(array_) (permutation_new(ARRAY_SIZE(array_)))
126
127 /**
128  * permutation_change - Advance to a new permutation
129  * @pi: Current permutation
130  *
131  * Advances @pi to the next permutation by the plain changes method
132  * (Steinhaus-Johnson-Trotter algorithm).
133  *
134  * Returns the elements which were swapped in @pi, or 0 if there are
135  * no more permutations.
136  */
137 permutation_swap_t permutation_change(struct permutation *pi);
138
139 /**
140  * permutation_change_array - Advance an array to a new permutation
141  * @pi: Current permutation
142  * @base: Address of array
143  * @size: Size of array elements
144  *
145  * Assuming the array at @base is currently in permutation @pi,
146  * advances @pi to the next permutation (as permutation_change()) and
147  * keeps the array in sync.
148  *
149  * Returns true if the permutation was advanced, false if there are no
150  * more permutations.
151  */
152 static inline bool permutation_change_array(struct permutation *pi,
153                                             void *base, size_t size)
154 {
155         permutation_swap_t swap = permutation_change(pi);
156
157         permutation_swap_mem(base, size, swap);
158         return (swap != 0);
159 }
160
161 static inline bool permutation_change_array_check_(struct permutation *pi,
162                                                    void *base, size_t size,
163                                                    int n)
164 {
165         assert(n == pi->n);
166         return permutation_change_array(pi, base, size);
167 }
168
169 /**
170  * PERMUTATION_CHANGE_ARRAY - Advance an array to a new permutation
171  * @pi_: Current permutation
172  * @a_: Array
173  *
174  * As permutation_change_array(), but operate on array @a_, which must
175  * be a C array declared with the same number of elements as @pi_.
176  */
177 #define PERMUTATION_CHANGE_ARRAY(pi_, a_)                               \
178         (permutation_change_array_check_((pi_), (a_),                   \
179                                          sizeof((a_)[0]), ARRAY_SIZE(a_)))
180
181 #endif /* CCAN_PERMUTATION_H */