97 lines
2.8 KiB
C
97 lines
2.8 KiB
C
#include "../includes/permutation.h"
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
permutation_generator_t PermutationNewGenerator(size_t len) {
|
|
size_t *permutation = malloc(2 * len * sizeof(size_t));
|
|
size_t *stack = permutation + len;
|
|
|
|
if (permutation == NULL) {
|
|
fprintf(stderr,
|
|
"Failed to allocate space for permutation array. Aborting.");
|
|
exit(EXIT_FAILURE);
|
|
}
|
|
|
|
permutation_generator_t generator = {
|
|
.len = len,
|
|
.permutation = permutation,
|
|
.stack = stack,
|
|
};
|
|
|
|
return generator;
|
|
}
|
|
|
|
void PermutationReset(permutation_generator_t *permutation_generator) {
|
|
size_t len = permutation_generator->len;
|
|
size_t *permutation = permutation_generator->permutation;
|
|
size_t *stack = permutation_generator->stack;
|
|
|
|
// Initialize the permutation array and stack.
|
|
for (size_t i = 0; i < len; i++) {
|
|
permutation[i] = i;
|
|
stack[i] = 0;
|
|
}
|
|
|
|
permutation_generator->pointer = 1;
|
|
permutation_generator->exhausted = (len == 0);
|
|
}
|
|
|
|
static void _PermutationNext(size_t *restrict permutation,
|
|
size_t *restrict stack, size_t *stack_ptr,
|
|
_Bool *exhausted, size_t len) {
|
|
repeat:
|
|
if (stack[*stack_ptr] < *stack_ptr) {
|
|
if (((*stack_ptr) & 1) == 0) { // Is even
|
|
// Swap A[0] and A[i]
|
|
size_t tmp = permutation[0];
|
|
permutation[0] = permutation[*stack_ptr];
|
|
permutation[*stack_ptr] = tmp;
|
|
} else {
|
|
// Swap A[c[i]] and A[i]
|
|
size_t tmp = permutation[*stack_ptr];
|
|
permutation[*stack_ptr] = permutation[stack[*stack_ptr]];
|
|
permutation[stack[*stack_ptr]] = tmp;
|
|
}
|
|
|
|
// Permutation can now be accessed.
|
|
|
|
stack[*stack_ptr] += 1;
|
|
*stack_ptr = 1;
|
|
} else {
|
|
stack[*stack_ptr] = 0;
|
|
*stack_ptr += 1;
|
|
if (*stack_ptr < len) {
|
|
goto repeat;
|
|
} else {
|
|
*exhausted = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
void PermutationNext(permutation_generator_t *permutation_generator) {
|
|
size_t *permutation = permutation_generator->permutation;
|
|
size_t *stack = permutation_generator->stack;
|
|
size_t *stack_ptr = &(permutation_generator->pointer);
|
|
size_t len = permutation_generator->len;
|
|
_Bool *exhausted = &(permutation_generator->exhausted);
|
|
_PermutationNext(permutation, stack, stack_ptr, exhausted, len);
|
|
}
|
|
|
|
void PermutationFree(permutation_generator_t *permutation_generator) {
|
|
free(permutation_generator->permutation);
|
|
// No need to free permutation_generator->stack, since it's contiguous.
|
|
}
|
|
|
|
void PrintPermutation(permutation_generator_t *permutation_generator) {
|
|
printf("(");
|
|
for (size_t i = 0; i < permutation_generator->len - 1; i++) {
|
|
printf("%zu, ", permutation_generator->permutation[i]);
|
|
}
|
|
if (permutation_generator->len > 0) {
|
|
printf("%zu)",
|
|
permutation_generator->permutation[permutation_generator->len - 1]);
|
|
} else {
|
|
printf(")");
|
|
}
|
|
} |