# Generating Stirling permutations

In contrast to Cayley permutations, Stirling permutations turn out to be very easy to generate by very small modifications to the Steinhaus–Johnson–Trotter algorithm.

A Stirling permutation is a permutation of a multiset with two copies of each value, with the property that between these two copies only larger values can appear. In particular, the two largest values must appear consecutively. The algorithm simply sweeps this consecutive largest pair back and forth across the sequence, recursing when the largest pair reaches one of the ends of the sequence. Each step is a swap of two items that are two positions apart; it isn't possible to move the two largest items by a swap of contiguous items.

For details see the updated PADS.Permutations.