First Blog Post – Permutation Generation Algorithms
mcochrane.com
mcochrane.com
A shorthand universal cycle a cyclic string containing every possible permutation of a given size N, where each sliding window of N-1 contains all of the information you need to generate a permutation of size N (since the final missing piece is implicit [whichever symbol is not present in the N-1 shorthand sliding window is the last symbol in the N-length permutation].
These require only N! space to encode all of the permutations of size N, and they can be generated recursively from a short-hand universal cycle the size below.
Ruskey and Williams have a series of fantastic papers on these, including generating permutations with pattern masks (preventing some of the permutations that match a pattern from being included in the resulting cycle).
> The python standard library already includes a number of combinatoric iterators such as combinations(), product() and of course permutations().
Only the last one is clickable.
This paper by Rainer Kemp has investigates the complexity: