The generation of random permutations on the fly (Q1111400): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(88)90210-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2079467789 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4773298 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Universal classes of hash functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4164569 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Fast Monte-Carlo Test for Primality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3707420 / rank | |||
Normal rank |
Latest revision as of 10:58, 19 June 2024
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