Generating permutations with given ups and downs

AbstractA permutation with a signature Q=(q1,q2,…,qn−1) where qi is either 1 or −1, is a permutation, P=π1,π2,…,πn, of the integers 1 to n such that qi(πi+1−πi) is positive for all 1⩽ i⩽n−1. Alternating permutations are an example of permutations with the signature (1,−1,1,−1,…). A constant average time algorithm is developed for generating all permutations with a given signature. Permutations are represented by a variant of their inversion tables. Ranking and unranking algorithms are also discussed