Practical algorithms for generating a random ordering of the elements of a weighted set

DOI10.1007/S00224-013-9496-6MaRDI QIDQ489756zbMATHOpenAlexFDO

Authors Kevin J. Lang

Publication date 21 January 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-013-9496-6

zbMATH Keywords

card shufflingrandom samplingpractical algorithmsrandom ordering

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40) Searching and sorting (68P10)

Recommendations

• Weighted random sampling with a reservoir
• Efficient sampling methods for discrete distributions
• Faster methods for random sampling
• scientific article; zbMATH DE number 437561
• Efficient sampling methods for discrete distributions

Cites work

• scientific article; zbMATH DE number 3815002 (Why is no real title available?)
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3558968 (Why is no real title available?)
• scientific article; zbMATH DE number 1303578 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• An Efficient Method for Generating Discrete Random Variables with General Distributions
• An Efficient Method for Weighted Sampling without Replacement
• Contemporary combinatorics. Collection of survey papers in combinatorics based on lectures given in the workshop on probabilistic combinatorics at the Paul Erdős Summer Research Center in Mathematics, Budapest, Hungary
• Dynamic generation of discrete random variates
• Elements of Information Theory
• Existence of optimal prefix codes for infinite source alphabets
• Fast algorithms for generating discrete random variates with changing distributions
• Generating Markov-Chain Transitions Quickly: II
• Introduction to algorithms
• Maintaining discrete probability distributions optimally
• The complexity of generating an exponentially distributed variate
• Trailing the dovetail shuffle to its lair

Cited in

(3)

• A Randomized In-Place Algorithm for Positioning the kth Element in a Multiset
• Weighted random sampling with a reservoir
• Parallel Weighted Random Sampling

This page was built for publication: Practical algorithms for generating a random ordering of the elements of a weighted set

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