Augustana University College

Sorted Lists of Random Numbers

Jonathan Mohr

There are applications in which it is useful to have a list of N random integers drawn from some integral range in sorted order. (Formally, we desire a sorted selection without replacement in which each selection occurs equiprobably.) For example, when a university sends evaluation forms to a random selection of former students of some professor who is being evaluated for promotion, it is very handy for an administrative assistant to be able to generate, for example, 100 random numbers in sorted order in the range 1 ... 263 (where we have addresses for 263 of the professor's former students). The output is required to be sorted because the list of names isn't numbered.

Reference: Jon Bentley, Programming Pearls, Chapter 11, citing Donald Knuth, Seminumerical Algorithms, §3.4.2, Algorithm S.

This page is an interface to a simple JavaScript program which (pseudo-) randomly generates the desired list of numbers and writes them into the text area below. This version differs slightly from the referenced algorithm in that we allow the range from which the random integers are to be selected to have an integer other than 1 as its lower bound. (Whether that's useful for some problem, who knows? Let me know if you have such a problem.)

WARNING: One reference I consulted indicated that Internet Explorer does not randomize the random number generator, so that the same list will be generated (for the same input parameters) each time the browser is restarted. Either a) use Netscape, Mozilla, Opera, Konqueror, etc., or b) generate a few lists of different sizes from different ranges before generating the actual list you want.

NOTE: If you have the opposite problem -- you want a random ordering of all the integers in some range -- see Randomly Scrambled Lists of Numbers

How many random numbers do you want?

What is the minimum number in the desired range of numbers?

What is the maximum number in the desired range of numbers?

Copyright © 2000, 2004 Jonathan Mohr