Skip to content

Instantly share code, notes, and snippets.

@ion1

ion1/sample-set-weights

Created August 10, 2015 16:56
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ion1/2e45a5199682da97af43 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ion1/2e45a5199682da97af43 to your computer and use it in GitHub Desktop.
Download ZIP
Sample an item from an ordered set with the proportional weights 1, 2, 3, …
Raw
sample-set-weights
Sample an item from an ordered set with the proportional weights 1, 2, 3, …:
tri x = (x·(x+1))/2
invtri x = (√(8·x+1)−1)/2
r ← uniform [0,1)
n = number of items
index = floor (invtri (r · tri n))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment