Generating Signed Permutations by Twisting Two-Sided Ribbons

We provide a simple approach to generating all \(2^n \cdot n!\) signed permutations of \([n] = \{1,2,\ldots ,n\}\) . Our solution generalizes the most famous ordering of permutations: plain changes (Steinhaus-Johnson-Trotter algorithm). In plain changes, the n! permutations of [n] are ordered so that successive permutations differ by swapping a pair of adjacent symbols, and the order is often visualized as a weaving pattern on n ropes. Here we model a signed permutation as n ribbons with two distinct sides, and each successive configuration is created by twisting (i.e., swapping and turning over) two neighboring ribbons or a single ribbon. By greedily prioritizing 2-twists of large symbols then 1-twists of large symbols, we create a signed version of plain change’s memorable zig-zag pattern. We also provide a loopless implementation (i.e., worst-case \(\mathcal {O}(1)\) -time per object) by enhancing the well-known mixed-radix Gray code algorithm.