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 s

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).