Generating permutations with given ups and downs

A 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.