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

DOI10.1007/S00224-013-9496-6MaRDI QIDQ489756zbMATH OpenOpenAlexFDO

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 shufflingpractical algorithmsrandom orderingrandom sampling

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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)

• Weighted random sampling with a reservoir
• A Randomized In-Place Algorithm for Positioning the kth Element in a Multiset
• 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)