34 lines
1005 B
Go
34 lines
1005 B
Go
package discovery
|
|
|
|
import (
|
|
"math/rand"
|
|
"time"
|
|
)
|
|
|
|
var r = rand.New(rand.NewSource(time.Now().UnixNano()))
|
|
|
|
// Shuffle pseudo-randomizes the order of elements.
|
|
// n is the number of elements. Shuffle panics if n < 0.
|
|
// swap swaps the elements with indexes i and j.
|
|
func Shuffle(n int, swap func(i, j int)) {
|
|
if n < 0 {
|
|
panic("invalid argument to Shuffle")
|
|
}
|
|
|
|
// Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
|
|
// Shuffle really ought not be called with n that doesn't fit in 32 bits.
|
|
// Not only will it take a very long time, but with 2³¹! possible permutations,
|
|
// there's no way that any PRNG can have a big enough internal state to
|
|
// generate even a minuscule percentage of the possible permutations.
|
|
// Nevertheless, the right API signature accepts an int n, so handle it as best we can.
|
|
i := n - 1
|
|
for ; i > 1<<31-1-1; i-- {
|
|
j := int(r.Int63n(int64(i + 1)))
|
|
swap(i, j)
|
|
}
|
|
for ; i > 0; i-- {
|
|
j := int(r.Int31n(int32(i + 1)))
|
|
swap(i, j)
|
|
}
|
|
}
|