The generation of random permutations on the fly
type: Item
instance of: scholarly article
title: The generation of random permutations on the fly
zbMATH Open document ID: 0658.68089
DOI: 10.1016/0020-0190(88)90210-4
author: Gilles Brassard
author: Sampath Kannan
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 4076657
zbMATH Keywords: real-time application
zbMATH Keywords: random permutation
zbMATH Keywords: data structure
zbMATH Keywords: rehashing
zbMATH Keywords: balanced tree
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90210-4
OpenAlex ID: W2079467789
cites work: Q4773298
cites work: Universal classes of hash functions
cites work: Q4164569
cites work: A Fast Monte-Carlo Test for Primality
cites work: Q3707420
description: scientific article; zbMATH DE number 4076657