permutation.h File Reference

Iterative (non-recursive!) permutation generator. More...

#include <stdint.h>
#include <stdbool.h>

Include dependency graph for permutation.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
bool	generateNextPermutation (uint8_t *first, uint8_t *last)
	Reorder an array of values to the next higher permutation.

Detailed Description

Iterative (non-recursive!) permutation generator.

Definition in file permutation.h.

Function Documentation

bool generateNextPermutation	(	uint8_t *	first,
		uint8_t *	last
	)

Reorder an array of values to the next higher permutation.

The "next higher" permuation is the one that is lexicographically one step higher than the input order. The order that would compare smaller to all other permutations is the one in which all elements are sorted in ascending order. This is the initial order that should be used in order to cycle through all possible permutations.

Typical usage example:

uint8_t myArray[] = { 1, 2, 3 };
do {
    // ... do something with current permuation of myArray
} while (generateNextPermutation(myArray, myArray + 3);

Remarks

This iterative permutation generation algorithm was taken, with slight modifications, from the GNU implementation of the C++ STL (libstdc++). It was chosen for for its lower memory usage over simpler and more common recursive implementations.

Returns

true if the next higher permutation could be generated, false otherwise

Definition at line 22 of file permutation.c.