random.md

Randomized algorithms

Table of contents

• Random sampling
  • Selection sampling
  • Reservoir sampling
• Random shuffling
  • Fisher–Yates algorithm

---

Random sampling

📖

• Sec. 3.4.2: Random sampling and shuffling – D.E.Knuth. The art of computer programming. Vol. 2: Seminumerical algorithms (1997)

Selection sampling

🔗

• Knuth’s algorithm S – Rosetta Code
• B.Rieck. A technique for selection sampling (sampling without replacement)

📄

• J.S.Vitter. An efficient algorithm for sequential random sampling – ACM Transactions on Mathematical Software 13, 58 (1987)

Reservoir sampling

🔗

• Reservoir sampling – Wikipedia

Random shuffling

📖

• Sec. 3.4.2: Random sampling and shuffling – D.E.Knuth. The art of computer programming. Vol. 2: Seminumerical algorithms (1997)

Fisher–Yates algorithm

🔗

• Fisher–Yates shuffle – Wikipedia
• Knuth shuffle – Rosetta Code