/* Copyright (C) 2015 by Alexandru Cojocaru */
/* This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see . */
package main
import (
"fmt"
"math"
"math/rand"
"time"
)
// http://www.cs.umd.edu/~samir/498/vitter.pdf
func sample(s []int) int {
r := s[0]
for i := 1; i < len(s); i++ {
j := rand.Int() % (i + 1)
if j == 0 {
r = s[i]
}
}
return r
}
type item struct {
w int
v int
}
// A-ES algorithm described in: http://arxiv.org/abs/1012.0256
func weightedSample(s []item) int {
var r int
var k float64
for _, i := range s {
g := math.Pow(rand.Float64(), 1/float64(i.w))
if g > k {
r = i.v
k = g
}
}
return r
}
func main() {
rand.Seed(time.Now().UnixNano())
fmt.Printf("%d\n", sample([]int{1, 2, 3, 4, 5, 6, 7, 8, 9}))
fmt.Printf("%d\n", weightedSample([]item{{3, 1}, {2, 2}, {1, 3}}))
}