On generating random permutations with arbitrary distributions

Oommen, J. (B. John)
Ng, D.T.H. (D. T H)

Publication date

August 1990

Abstract

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 lis...

Extracted data

We use cookies to provide a better user experience.

Data Protection

On generating random permutations with arbitrary distributions

Abstract

Extracted data

On generating random permutations with arbitrary distributions

Abstract

Extracted data

Related items

Related items