Last active
October 26, 2016 16:36
-
-
Save MaxHalford/1c2890bf7639a9578c0c184c6e96508d to your computer and use it in GitHub Desktop.
Sampling k numbers in range [a, b) without replacement - Two different ways
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import "fmt" | |
// Sample k unique integers in range [min, max) by generating | |
// random numbers between min and max and then taking the first | |
// k numbers. | |
// The downside to this algorithm is a temporary | |
// list has to be kept in memory to store all the number from | |
// min to max. | |
// The upside is that the resulting number will be | |
// in a random order. | |
func randomInts(min, max, k int, rng *rand.Rand) (ints []int) { | |
ints = make([]int, k) | |
var choices = rng.Perm(max - min) | |
for i := 0; i < k; i++ { | |
ints[i] = choices[i] + min | |
} | |
return | |
} | |
func main() { | |
var rng = rand.New(rand.NewSource(time.Now().UnixNano())) | |
fmt.Println(randomInts(3, 10, 2, rng)) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import "fmt" | |
// Sample k unique integers in range [min, max) using reservoir sampling, | |
// specifically Vitter's Algorithm R. | |
// The upside is that no temporary list has to be maintained. | |
// The downside is that the resulting numbers are not necessarily in a | |
// random order. | |
func randomInts(min, max, k int, rng *rand.Rand) (ints []int) { | |
ints = make([]int, k) | |
for i := 0; i < k; i++ { | |
ints[i] = i + min | |
} | |
var j int | |
for i := k; i < max-min; i++ { | |
j = rng.Intn(i + 1) | |
if j < k { | |
ints[j] = i + min | |
} | |
} | |
return | |
} | |
func main() { | |
var rng = rand.New(rand.NewSource(time.Now().UnixNano())) | |
fmt.Println(randomInts(3, 10, 2, rng)) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment