From c3e9a05832ec5362bf108a7f1487aa4dcff96f99 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Tue, 29 Sep 2015 00:59:17 +1000 Subject: [PATCH 1/1] permutation: Generate permutations of arrays New module. Signed-off-by: David Gibson --- Makefile-ccan | 1 + ccan/permutation/LICENSE | 1 + ccan/permutation/_info | 61 +++++++++++ ccan/permutation/permutation.c | 100 ++++++++++++++++++ ccan/permutation/permutation.h | 181 +++++++++++++++++++++++++++++++++ ccan/permutation/test/api.c | 147 ++++++++++++++++++++++++++ 6 files changed, 491 insertions(+) create mode 120000 ccan/permutation/LICENSE create mode 100644 ccan/permutation/_info create mode 100644 ccan/permutation/permutation.c create mode 100644 ccan/permutation/permutation.h create mode 100644 ccan/permutation/test/api.c diff --git a/Makefile-ccan b/Makefile-ccan index fb7e4c9b..b8390fb7 100644 --- a/Makefile-ccan +++ b/Makefile-ccan @@ -88,6 +88,7 @@ MODS_WITH_SRC := aga \ ogg_to_pcm \ opt \ order \ + permutation \ pr_log \ ptrint \ ptr_valid \ diff --git a/ccan/permutation/LICENSE b/ccan/permutation/LICENSE new file mode 120000 index 00000000..dc314eca --- /dev/null +++ b/ccan/permutation/LICENSE @@ -0,0 +1 @@ +../../licenses/LGPL-2.1 \ No newline at end of file diff --git a/ccan/permutation/_info b/ccan/permutation/_info new file mode 100644 index 00000000..4998f5db --- /dev/null +++ b/ccan/permutation/_info @@ -0,0 +1,61 @@ +#include "config.h" +#include +#include +#include + +/** + * permutation - Generate permutations + * + * This module allows you to generate all permutations of a given + * number of elements. It can also modify a user-supplied array in + * place through all those permutations. + * + * It uses the "plain changes" method, aka the + * Steinhaus-Johnson-Trotter algorithm to generate the permtations. + * This has some advantages over a naive recursive algorithm: + * + * - Each permutation is generated from the last by a single swap of + * adjacent elements + * + * - Constructing each permutation in place from the last takes + * amortized O(1) time. + * + * License: LGPL (v2.1 or any later version) + * Example: + * // Given "1 2 3" outputs 1 2 3 1 3 2 3 1 2 3 2 1 2 3 1 2 1 3 + * #include + * #include + * + * int main(int argc, char *argv[]) + * { + * int i; + * struct permutation *pi = permutation_new(argc - 1); + * + * do { + * for (i = 1; i < argc; i++) + * printf("%s ", argv[i]); + * printf("\n"); + * } while (permutation_change_array(pi, + * &argv[1], sizeof(argv[1]))); + * exit(0); + * } + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/build_assert\n"); + printf("ccan/mem\n"); + return 0; + } + + if (strcmp(argv[1], "testdepends") == 0) { + printf("ccan/array_size\n"); + return 0; + } + + return 1; +} diff --git a/ccan/permutation/permutation.c b/ccan/permutation/permutation.c new file mode 100644 index 00000000..19139d5d --- /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 + +#include +#include +#include + +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; +} diff --git a/ccan/permutation/permutation.h b/ccan/permutation/permutation.h new file mode 100644 index 00000000..c4d647ac --- /dev/null +++ b/ccan/permutation/permutation.h @@ -0,0 +1,181 @@ +/* Licensed under LGPLv2.1+ - see LICENSE file for details */ +#ifndef CCAN_PERMUTATION_H +#define CCAN_PERMUTATION_H + +#include + +#include +#include +#include +#include + +#include +#include + +/* + * We limit the number of elements to 64, to keep our data structures + * neat. That seems low, but even 64! permutations is far too many to + * really generate in practice. + */ +#define PERMUTATION_MAX_SHIFT 6 +#define PERMUTATION_MAX_ITEMS (1 << PERMUTATION_MAX_SHIFT) + +/** + * struct permutation - represents a permutation + * + * The fields here are user visible, but it's allocated internally + * with extra state information appended. + * + * @n: Number of elements in the permutation + * @v: values 0..(n-1) arranged in current permutation + */ +struct permutation { + int n; + uint8_t v[]; + /* Private state data follows */ +}; + + +/** + * permutation_count - determine number of permutations + * @n: Number of elements + * + * Returns the number of permutations of @n elements. + */ +unsigned long long permutation_count(int n); + +/** + * permutation_swap_t - represents a swap of two items + * + * Encodes a swap of two elements in an array. Should be treated as + * opaque, except that 0 always represents "swap nothing". + */ +typedef unsigned permutation_swap_t; + + +/** + * permutation_swap_a - first item to swap + * permutation_swap_b - second item to swap + */ +static inline int permutation_swap_a(permutation_swap_t swap) +{ + return swap % PERMUTATION_MAX_ITEMS; +} + +static inline int permutation_swap_b(permutation_swap_t swap) +{ + return swap / PERMUTATION_MAX_ITEMS; +} + +/** + * permutation_swap - swap two elements in an array + * @base: address of array + * @size: size of each array element + * @swap: which elements to swap + * + * Swaps the elements at index permutation_swap_a(@swap) and + * permutation_swap_b(@swap) in the array at @base of items of size + * @size. + */ +static inline void permutation_swap_mem(void *base, size_t size, + permutation_swap_t swap) +{ + char *ap = (char *)base + (permutation_swap_a(swap) * size); + char *bp = (char *)base + (permutation_swap_b(swap) * size); + + BUILD_ASSERT(sizeof(permutation_swap_t) * 8 + >= PERMUTATION_MAX_SHIFT * 2); + + if (!swap) + return; + + memswap(ap, bp, size); +} + +/** + * PERMUTATION_SWAP - swap two elements in an array + * @a_: array + * @swap_: which elements to swap + * + * As permutation_swap(), but must act on a C array declared at the + * right size. + */ +#define PERMUTATION_SWAP(a_, swap_) \ + do { \ + permutation_swap((a_), sizeof((a_)[0]), (swap_)); \ + } while (0) + + +/** + * permutation_new - allocates a new identity permutation + * @n: Number of elements + * + * Allocates and initializes a new permutation of @n elements. + * Initially it represents the identity permutation. + */ +struct permutation *permutation_new(int n); + +/** + * PERMUTATION_NEW - allocates a new identity permutation of an array + * @array_: Array to permute + * + * As permutation_new() but take the number of elements from the + * declaration of @array_. + */ +#define PERMUTATION_NEW(array_) (permutation_new(ARRAY_SIZE(array_))) + +/** + * permutation_change - Advance to a new permutation + * @pi: Current permutation + * + * Advances @pi to the next permutation by the plain changes method + * (Steinhaus-Johnson-Trotter algorithm). + * + * Returns the elements which were swapped in @pi, or 0 if there are + * no more permutations. + */ +permutation_swap_t permutation_change(struct permutation *pi); + +/** + * permutation_change_array - Advance an array to a new permutation + * @pi: Current permutation + * @base: Address of array + * @size: Size of array elements + * + * Assuming the array at @base is currently in permutation @pi, + * advances @pi to the next permutation (as permutation_change()) and + * keeps the array in sync. + * + * Returns true if the permutation was advanced, false if there are no + * more permutations. + */ +static inline bool permutation_change_array(struct permutation *pi, + void *base, size_t size) +{ + permutation_swap_t swap = permutation_change(pi); + + permutation_swap_mem(base, size, swap); + return (swap != 0); +} + +static inline bool permutation_change_array_check_(struct permutation *pi, + void *base, size_t size, + int n) +{ + assert(n == pi->n); + return permutation_change_array(pi, base, size); +} + +/** + * PERMUTATION_CHANGE_ARRAY - Advance an array to a new permutation + * @pi_: Current permutation + * @a_: Array + * + * As permutation_change_array(), but operate on array @a_, which must + * be a C array declared with the same number of elements as @pi_. + */ +#define PERMUTATION_CHANGE_ARRAY(pi_, a_) \ + (permutation_change_array_check_((pi_), (a_), \ + sizeof((a_)[0]), ARRAY_SIZE(a_))) + +#endif /* CCAN_PERMUTATION_H */ diff --git a/ccan/permutation/test/api.c b/ccan/permutation/test/api.c new file mode 100644 index 00000000..de929611 --- /dev/null +++ b/ccan/permutation/test/api.c @@ -0,0 +1,147 @@ +#include "config.h" + +#include +#include +#include +#include + +#include +#include +#include + +#define MAX_ITEMS 10 + +#define PERMUTE(pi, arr) \ + do { \ + ok1(PERMUTATION_CHANGE_ARRAY((pi), (arr))); \ + } while (0) + +#define CHECK_ORDER(a, t, ...) \ + do { \ + t cmp[] = { __VA_ARGS__ }; \ + ok1(memcmp((a), cmp, sizeof(cmp)) == 0); \ + } while (0) + +#define WORDLEN 6 +typedef char word[WORDLEN]; + +int main(void) +{ + struct permutation *pi; + int single = 12345; + char pair[] = { 'P', 'Q' }; + uint16_t triple[] = {7, 9, 1000}; + word four[] = {"ZERO", "ONE", "TWO", "THREE"}; + int i; + + plan_tests(2 * permutation_count(1) + 1 + + 2 * permutation_count(2) + 1 + + 2 * permutation_count(3) + 1 + + 2 * permutation_count(4) + 1 + + MAX_ITEMS + 1); + + /* One */ + pi = permutation_new(1); + CHECK_ORDER(&single, int, 12345); + ok1(!permutation_change_array(pi, &single, sizeof(single))); + CHECK_ORDER(&single, int, 12345); + free(pi); + + /* Pair */ + pi = PERMUTATION_NEW(pair); + CHECK_ORDER(pair, char, 'P', 'Q'); + PERMUTE(pi, pair); + CHECK_ORDER(pair, char, 'Q', 'P'); + ok1(!PERMUTATION_CHANGE_ARRAY(pi, pair)); + CHECK_ORDER(pair, char, 'Q', 'P'); + free(pi); + + /* Triple */ + pi = PERMUTATION_NEW(triple); + CHECK_ORDER(triple, uint16_t, 7, 9, 1000); + PERMUTE(pi, triple); + CHECK_ORDER(triple, uint16_t, 7, 1000, 9); + PERMUTE(pi, triple); + CHECK_ORDER(triple, uint16_t, 1000, 7, 9); + PERMUTE(pi, triple); + CHECK_ORDER(triple, uint16_t, 1000, 9, 7); + PERMUTE(pi, triple); + CHECK_ORDER(triple, uint16_t, 9, 1000, 7); + PERMUTE(pi, triple); + CHECK_ORDER(triple, uint16_t, 9, 7, 1000); + ok1(!PERMUTATION_CHANGE_ARRAY(pi, triple)); + CHECK_ORDER(triple, uint16_t, 9, 7, 1000); + free(pi); + + /* Four */ + pi = PERMUTATION_NEW(four); + CHECK_ORDER(four, word, "ZERO", "ONE", "TWO", "THREE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ZERO", "ONE", "THREE", "TWO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ZERO", "THREE", "ONE", "TWO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "THREE", "ZERO", "ONE", "TWO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "THREE", "ZERO", "TWO", "ONE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ZERO", "THREE", "TWO", "ONE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ZERO", "TWO", "THREE", "ONE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ZERO", "TWO", "ONE", "THREE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "TWO", "ZERO", "ONE", "THREE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "TWO", "ZERO", "THREE", "ONE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "TWO", "THREE", "ZERO", "ONE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "THREE", "TWO", "ZERO", "ONE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "THREE", "TWO", "ONE", "ZERO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "TWO", "THREE", "ONE", "ZERO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "TWO", "ONE", "THREE", "ZERO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "TWO", "ONE", "ZERO", "THREE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ONE", "TWO", "ZERO", "THREE"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ONE", "TWO", "THREE", "ZERO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ONE", "THREE", "TWO", "ZERO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "THREE", "ONE", "TWO", "ZERO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "THREE", "ONE", "ZERO", "TWO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ONE", "THREE", "ZERO", "TWO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ONE", "ZERO", "THREE", "TWO"); + PERMUTE(pi, four); + CHECK_ORDER(four, word, "ONE", "ZERO", "TWO", "THREE"); + ok1(!PERMUTATION_CHANGE_ARRAY(pi, four)); + CHECK_ORDER(four, word, "ONE", "ZERO", "TWO", "THREE"); + free(pi); + + for (i = 0; i <= MAX_ITEMS; i++) { + uint64_t nperms = 1; + + diag("Counting permutations of %d\n", i); + + pi = permutation_new(i); + while (permutation_change(pi)) + nperms++; + + ok(nperms == permutation_count(i), + "%"PRId64" permutations of %d (%d! == %lld)", + nperms, i, i, permutation_count(i)); + free(pi); + } + + /* This exits depending on whether all tests passed */ + + return exit_status(); +} -- 2.39.2