Let R = {R1,R2,....,RM} be an ordered set of M elements where Ri<Rj whenever i<j. Let π be the set of permutations of R. We consider the problem of randomly generating the elements of π according to a distribution G(π). Various algorithms including those due to Durstenfeld3.5 and Moses et al7 are available for the case when the distribution G(π) is a uniform distribution (i.e., where all the elements of π are generated with equal probability). In this paper we consider the case when the distribution G(π) is not necessarily uniform. We present a strategy for specifying the distribution G(π) and propose a technique for generating the elements of π according to the distribution G(π). Applications of the technique to generate 'almost sorted lists' and in the Travelling Salesman Problem have been presented. Finally, simulation results have been included which demonstrate the power of the Random Permutation Generation (RPG) technique.

Additional Metadata
Journal Computer Journal
Citation
Oommen, J, & Ng, D.T.H. (D. T H). (1990). On generating random permutations with arbitrary distributions. Computer Journal, 33(4), 368–374.