The generation of random permutations on the fly

DOI10.1016/0020-0190(88)90210-4MaRDI QIDQ1111400zbMATH OpenOpenAlexFDO

Authors Gilles Brassard, Sampath Kannan

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90210-4

zbMATH Keywords

balanced treedata structurerandom permutationreal-time applicationrehashing

Mathematics Subject Classification ID

Data structures (68P05) Discrete mathematics in relation to computer science (68R99)

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.

Recommendations

• Observations on the generation of permutations from random sequences
• scientific article; zbMATH DE number 176751
• In-place random list permutations
• Random permutations on distributed, external and hierarchical memory
• Fast generation of random permutations via networks simulation

Cites work

• A Fast Monte-Carlo Test for Primality
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Universal classes of hash functions

Cited in

(11)

• A note on unscrambling address lines
• Random list permutations in place
• Fast generation of random permutations via networks simulation
• Unicyclic strong permutations
• Integrated strategy for generating permutation
• scientific article; zbMATH DE number 4199437 (Why is no real title available?)
• Observations on the generation of permutations from random sequences
• Shift-Generated Random Permutations and The M/D/1 Queue
• scientific article; zbMATH DE number 871160 (Why is no real title available?)
• scientific article; zbMATH DE number 2216957 (Why is no real title available?)
• In-place random list permutations

This page was built for publication: The generation of random permutations on the fly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111400)