A parallel algorithm for the generation of a permutation and applications

AbstractA parallel algorithm is presented for generating a permutation of size n. The algorithm uses O(n) processors and runs in O(Log2(n)) time. We show also that this algorithm permits the generation of a Dyck word. The same techniques work for Motzkin words, left factors of Dyck or Motzkin words and words which are in bijection with trees split into patterns as defined by Dershowitz and Zaks (1989) (see Alonso, 1992)