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

DOI10.1007/S00224-013-9496-6zbMATH Open1303.68168OpenAlexW2175577357MaRDI QIDQ489756FDOQ489756

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

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

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)

Cites Work

• Title not available (Why is that?)
• Elements of Information Theory
• Dynamic generation of discrete random variates
• Introduction to algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trailing the dovetail shuffle to its lair
• Title not available (Why is that?)
• An Efficient Method for Generating Discrete Random Variables with General Distributions
• Title not available (Why is that?)
• Maintaining discrete probability distributions optimally
• 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
• The complexity of generating an exponentially distributed variate
• An Efficient Method for Weighted Sampling without Replacement
• Generating Markov-Chain Transitions Quickly: II
• Title not available (Why is that?)
• Existence of optimal prefix codes for infinite source alphabets
• Fast algorithms for generating discrete random variates with changing distributions

Cited In (3)

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

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)