FAST GENERATION OF RANDOM PERMUTATIONS VIA NETWORKS SIMULATION

We consider the problem of generating random permutations with uniform distribution. That is, we require that for an arbitrary permutation p i of n elements, with probability 1/n! the machine halts with the ith output cell containing pi(i), for 1 less than or equal to i less than or equal to n, We study this problem on two models of parallel computa tions: the CREW PRAM and the EREW PRAM. The main result of the paper i s an algorithm for generating random permutations that runs in O(log l og n) time and uses O(n (1+o(1))) processors on the CREW PRAM. This is the first o(log n)-time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permut ation in time O (log n) using n processors and O(n) space. This algori thm outperforms each of the previously known algorithms for the exclus ive write PRAMs. The common and novel feature of both our algorithms i s first to design a suitable random switching network generating a per mutation and then to simulate this network on the PRAM model in a fast way.