#iterator #permutation #generate #recursion #modification #iteratively #time


Generate permutations iteratively without recursion in O(n) time

2 releases

0.1.1 Feb 24, 2023
0.1.0 Feb 24, 2023

#34 in #modification

MIT license

93 lines


An iterative permutation generator without recursion for Rust.

Iterator Permutations::of(n) generates permutations of 0..n iteratively using Steinhaus-Johnson-Trotter algorithm with Even's modification.

Each next() call has $O(n)$ time and space complexity.

Not optimized. At all. Any improvements are welcome.

Published under MIT license.


Generate permutations iteratively without recursion.

Permutations.of(n) function generates an iterator instance for permutations of 0..n.

Permutations.next() uses Steinhaus-Johnson-Trotter algorithm with Even's modification to generate the next permutation in $O(n)$ time.

Each iterator is one-way. You need to construct a new one for iterating again.

No runtime deps