Skip to content

Random.md

Latest commit

 

History

History
27 lines (22 loc) · 1.57 KB

Random.md

File metadata and controls

27 lines (22 loc) · 1.57 KB

Random

Concepts

  • Randomly get one or more candidates from a collection.

Types

Type Example Range Presentation
Each candidate with same weight/probability dw2 dw4
Each candidate with different weights/probabilities dw1 dw3

Transform between Types

Each candidate with same weight/probability Each candidate with different weights/probabilities
[3, 3, 4, 5, 6, 6, 6, 7] = [{3, 2}, {4, 1}, {5, 1}, {6, 3}, {7, 1}]

Strategies

  • For getting random candidate with same weight, consider using Reservoir Sampling
  • For getting random candidate with different weight, consider using Prefix Sum Array
  • You can also consider converting the problem into another type of random problem and use corresponding solution pattern.

Problem