3 ms·

First Blog Post – Permutation Generation Algorithms

• mcochrane 4y ago
  I'd love feedback from anyone who reads it :)
  • muth02446 4y ago
    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: https://link.springer.com/article/10.1007/s002360050114 https://link.springer.com/article/10.1007/s002360050114
• gus_massa 4y ago
  Minor nitpick: > 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.
• kian 4y ago
  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).