50 lines
1.8 KiB
C
50 lines
1.8 KiB
C
#ifndef ACED_INCLUDES_PERMUTATION_H_
|
|
#define ACED_INCLUDES_PERMUTATION_H_
|
|
|
|
// The permutations are generated according to Heap's method [1].
|
|
// Because we're not allowed to "yield" (i.e., we don't have co-routines, etc.),
|
|
// we use a state machine (given by `permutation_generator_t`), adapting the
|
|
// iterative version of Heap's method to suit this approach.
|
|
//
|
|
// References:
|
|
// [1]: https://en.m.wikipedia.org/wiki/Heap%27s_algorithm
|
|
|
|
#include <stdbool.h>
|
|
#include <stddef.h>
|
|
|
|
typedef struct {
|
|
size_t len; // The number of elements being permuted.
|
|
size_t *restrict permutation; // Current permutation, as indices.
|
|
_Bool exhausted; // Whether there are any permutations left to generate.
|
|
size_t *restrict stack;
|
|
size_t pointer;
|
|
} permutation_generator_t;
|
|
|
|
// Create a `permutation_generator_t`.
|
|
// This needs to be done only once. Afterwards, use only `PermutationReset`.
|
|
// After getting a new generator, you still need to call `PermutationReset`, or
|
|
// behaviour is undefined.
|
|
//
|
|
// Arguments:
|
|
// len Number of elements to permute (from `0` to `len-1`).
|
|
permutation_generator_t PermutationNewGenerator(size_t len);
|
|
|
|
// Configure a permutation generator to start generating permutations from the
|
|
// start.
|
|
void PermutationReset(permutation_generator_t *permutation_generator);
|
|
|
|
// Generate the next permutation.
|
|
//
|
|
// Calling this after `permutation_generator->exhausted` is true results in
|
|
// undefined behaviour.
|
|
void PermutationNext(permutation_generator_t *permutation_generator);
|
|
|
|
// Release the memory associated to a permutation generator.
|
|
//
|
|
// This will invalidate the generator.
|
|
void PermutationFree(permutation_generator_t *permutation_generator);
|
|
|
|
// Print the current permutation of a generator.
|
|
void PrintPermutation(permutation_generator_t *permutation_generator);
|
|
|
|
#endif // ACED_INCLUDES_PERMUTATION_H_
|