Observations on the generation of permutations from random sequences

Abstract

Several algorithms for generating random permutations are examined relative to their random characteristics and their efficiency. It is noted that uniformly-distributed permutations cannot be generated by sampling a finite portion of a random sequence. An algorithm is constructed which includes as a special case the generation of permutations using n[log n]−(2^[logn]−1) bits per permutation.

Keywords:

• Random permutations
• efficient algorithms
• sampling without replacement
• shuffling

C.R. Categories:

• F.2.2
• G.2.1
• G.3
• G.4