If you generate permutations in lexicographic order one at a time, you only need
to change suffix of the previous permutation which should be faster than O(n * n!)
This paper by Rainer Kemp has investigates the complexity:
You can generate and encode permutations in a manner that is simple, fast, and compact using shorthand universal cycles.
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).
4 comments
[ 4.8 ms ] story [ 212 ms ] threadThis paper by Rainer Kemp has investigates the complexity:
https://link.springer.com/article/10.1007/s002360050114
> 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.
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).