The generation of random permutations on the fly (Q1111400)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The generation of random permutations on the fly |
scientific article |
Statements
The generation of random permutations on the fly (English)
0 references
1988
0 references
How should one generate a random permutation if only a small but unpredictable subset of its domain is ever to be queried? This paper offers three different solutions to this problem. The choice between them depends on the availability of resources such as time and space. Our fastest solution displays the curious phenomenon of requiring more memory space than it has time to use. We also introduce two new data structure techniques: continuous rehashing and a balanced tree scheme that allows efficiently finding the jth element not in a set.
0 references
real-time application
0 references
random permutation
0 references
data structure
0 references
rehashing
0 references
balanced tree
0 references