TR-138: On Generating Random Permutations with Arbitrary Distributions

Abstract

Let = {R1 ,R2, .. ,,RM} be an ordered set of M elements where Ri < Rj whenever i < j. Let 7t be the set of permutations of 1. We consider the problem of randomly generating the elements of 7t according to a distribution G(7t). Various algorithms including those due to Durstenfeld [D2, K1] and Moses et al [M1] are available for the case when the distribution G(7t) is a uniform distribution (i.e., where all the elements of 7t are generated with equal probability). In this paper we consider the case when the distribution G(7t) is not necessarily uniform. We present a strategy for specifying the distribution G(7t) and propose a technique for generating the elements of the 7t according to the distribution G(7t). 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.