在Go中对数组进行洗牌

huangapple go评论96阅读模式
英文:

shuffle array in Go

问题

我试图将以下Python代码翻译成Go:

import random

list = [i for i in range(1, 25)]
random.shuffle(list)
print(list)

但是我发现我的Go版本冗长而笨拙,因为没有shuffle函数,我不得不实现接口并转换类型。

有没有一种符合Go语言习惯的版本?

英文:

I tried to translate the following Python code to Go

import random

list = [i for i in range(1, 25)]
random.shuffle(list)
print(list)

but found my Go version lengthy and awkward because there is no shuffle function and I had to implement interfaces and convert types.

What would be an idiomatic Go version of my code?

答案1

得分: 116

dystroy的答案是完全合理的,但也有可能在不分配任何额外切片的情况下进行洗牌。

for i := range slice {
    j := rand.Intn(i + 1)
    slice[i], slice[j] = slice[j], slice[i]
}

有关该算法的更多详细信息,请参阅维基百科文章rand.Perm实际上也在内部使用这个算法。

英文:

dystroy's answer is perfectly reasonable, but it's also possible to shuffle without allocating any additional slices.

for i := range slice {
    j := rand.Intn(i + 1)
    slice[i], slice[j] = slice[j], slice[i]
}

See this Wikipedia article for more details on the algorithm. rand.Perm actually uses this algorithm internally as well.

答案2

得分: 105

作为你的列表只是从1到25的整数,你可以使用Perm

list := rand.Perm(25)
for i, _ := range list {
    list[i]++
}

请注意,使用rand.Perm给出的排列是洗牌任何数组的有效方法。

dest := make([]int, len(src))
perm := rand.Perm(len(src))
for i, v := range perm {
	dest[v] = src[i]
}
英文:

As your list is just the integers from 1 to 25, you can use Perm :

list := rand.Perm(25)
for i, _ := range list {
    list[i]++
}

Note that using a permutation given by rand.Perm is an effective way to shuffle any array.

dest := make([]int, len(src))
perm := rand.Perm(len(src))
for i, v := range perm {
	dest[v] = src[i]
}

答案3

得分: 74

自从1.10版本开始,Go语言包含了一个官方的Fisher-Yates shuffle函数。

文档:pkg/math/rand/#Shuffle

> ## math/rand: 添加Shuffle函数
>
> Shuffle函数使用Fisher-Yates算法。
>
> 由于这是一个新的API,它使我们有机会使用一个更快的Int31n实现,它大部分避免了除法操作。
>
> 结果是,BenchmarkPerm30ViaShuffleBenchmarkPerm30快约30%,
尽管它需要一个单独的初始化循环
并使用函数调用来交换元素。

还可以参考原始的CL 51891

首先,如shelll所评论的:

> 不要忘记给随机数种子,否则你将始终得到相同的顺序。
例如rand.Seed(time.Now().UnixNano())

示例:

words := strings.Fields("ink runs from the corners of my mouth")
rand.Shuffle(len(words), func(i, j int) {
    words[i], words[j] = words[j], words[i]
})
fmt.Println(words)
英文:

Since 1.10 Go includes an official Fisher-Yates shuffle function.

Documentation: pkg/math/rand/#Shuffle

> ## math/rand: add Shuffle
>
> Shuffle uses the Fisher-Yates algorithm.
>
> Since this is new API, it affords us the opportunity
to use a much faster Int31n implementation that mostly avoids division.
>
> As a result, BenchmarkPerm30ViaShuffle is
about 30% faster than BenchmarkPerm30,
despite requiring a separate initialization loop
and using function calls to swap elements.

See also the original CL 51891

First, as commented by shelll:

> Do not forget to seed the random, or you will always get the same order.
For example rand.Seed(time.Now().UnixNano())

Example:

words := strings.Fields("ink runs from the corners of my mouth")
rand.Shuffle(len(words), func(i, j int) {
    words[i], words[j] = words[j], words[i]
})
fmt.Println(words)

答案4

得分: 10

Answer by Evan Shaw有一个小bug。如果我们按照最低索引到最高索引的顺序遍历切片,以获得一个均匀(伪)随机的洗牌,根据同一篇文章,我们必须从区间[i,n)中选择一个随机整数,而不是[0,n+1)

这个实现对于较大的输入可以满足你的需求,但对于较小的切片,它会执行一个非均匀的洗牌。

为了利用rand.Intn(),我们可以这样做:

	for i := len(slice) - 1; i > 0; i-- {
		j := rand.Intn(i + 1)
		slice[i], slice[j] = slice[j], slice[i]
	}

按照维基百科文章中的相同算法进行操作。

英文:

Answer by Evan Shaw has a minor bug. If we iterate through the slice from lowest index to highest, to get a uniformly (pseudo) random shuffle, according to the same article, we must choose a random integer from interval [i,n) as opposed to [0,n+1).

That implementation will do what you need for larger inputs, but for smaller slices, it will perform a non-uniform shuffle.

To utilize rand.Intn(), we can do:

	for i := len(slice) - 1; i > 0; i-- {
		j := rand.Intn(i + 1)
		slice[i], slice[j] = slice[j], slice[i]
	}

following the same algorithm from Wikipedia article.

答案5

得分: 4

也许你还可以使用以下函数:

func main() {
    slice := []int{10, 12, 14, 16, 18, 20}
    Shuffle(slice)
    fmt.Println(slice)
}

func Shuffle(slice []int) {
    r := rand.New(rand.NewSource(time.Now().Unix()))
    for n := len(slice); n > 0; n-- {
        randIndex := r.Intn(n)
        slice[n-1], slice[randIndex] = slice[randIndex], slice[n-1]
    }
}
英文:

Maybe you can also use the following function:

func main() {
   slice := []int{10, 12, 14, 16, 18, 20}
   Shuffle(slice)
   fmt.Println(slice)
}

func Shuffle(slice []int) {
   r := rand.New(rand.NewSource(time.Now().Unix()))
   for n := len(slice); n > 0; n-- {
	  randIndex := r.Intn(n)
	  slice[n-1], slice[randIndex] = slice[randIndex], slice[n-1]
   }
}

答案6

得分: 2

使用math/rand库中的Shuffle()函数。

以下是一个示例:

package main

import (
	"fmt"
	"math/rand"
	"strings"
)

func main() {
	words := strings.Fields("ink runs from the corners of my mouth")
	rand.Shuffle(len(words), func(i, j int) {
		words[i], words[j] = words[j], words[i]
	})
	fmt.Println(words)
}

由于它来自math/rand库,需要进行种子初始化。更多详情请参见这里

英文:

Use Shuffle() from the math/rand library.

Here's an example:

package main

import (
	"fmt"
	"math/rand"
	"strings"
)

func main() {
	words := strings.Fields("ink runs from the corners of my mouth")
	rand.Shuffle(len(words), func(i, j int) {
		words[i], words[j] = words[j], words[i]
	})
	fmt.Println(words)
}

Since it comes from the math/rand library it needs to be seeded. See here for more details.

答案7

得分: 1

当使用math/rand包时,不要忘记设置一个源

// 随机数是由源生成的。顶级函数,如Float64和Int,使用一个默认的共享源,每次运行程序时都会产生一个确定性的值序列。如果需要每次运行时都有不同的行为,请使用Seed函数初始化默认源。

所以我写了一个Shuffle函数来考虑这个问题:

import (
"math/rand"
)

func Shuffle(array []interface{}, source rand.Source) {
random := rand.New(source)
for i := len(array) - 1; i > 0; i-- {
j := random.Intn(i + 1)
array[i], array[j] = array[j], array[i]
}
}

使用方法如下:

source := rand.NewSource(time.Now().UnixNano())
array := []interface{}{"a", "b", "c"}

Shuffle(array, source) // [c b a]

如果您想使用它,可以在这里找到它 https://github.com/shomali11/util

英文:

When using the math/rand package, do not forget to set a source

// Random numbers are generated by a Source. Top-level functions, such as
// Float64 and Int, use a default shared Source that produces a deterministic
// sequence of values each time a program is run. Use the Seed function to
// initialize the default Source if different behavior is required for each run.

So I wrote a Shuffle function that takes this into consideration:

import (
    "math/rand"
)

func Shuffle(array []interface{}, source rand.Source) {
    random := rand.New(source)
    for i := len(array) - 1; i > 0; i-- {
	    j := random.Intn(i + 1)
	    array[i], array[j] = array[j], array[i]
    }
}

And to use it:

source := rand.NewSource(time.Now().UnixNano())
array := []interface{}{"a", "b", "c"}

Shuffle(array, source) // [c b a]

If you would like to use it, you can find it here https://github.com/shomali11/util

答案8

得分: 1

Raed的方法因为[]interface{}作为输入而非常不灵活。这里是更方便的go>=1.8版本:

func Shuffle(slice interface{}) {
    rv := reflect.ValueOf(slice)
    swap := reflect.Swapper(slice)
    length := rv.Len()
    for i := length - 1; i > 0; i-- {
        j := rand.Intn(i + 1)
        swap(i, j)
    }
}

示例用法:

rand.Seed(time.Now().UnixNano()) // 在应用程序初始化期间执行一次
s := []int{1, 2, 3, 4, 5}
Shuffle(s)
fmt.Println(s) // 示例输出:[4 3 2 1 5]

还有,不要忘记“少依赖比少复制要好一些”(a little copying is better than a little dependency)。

英文:

Raed's approach is very inflexible because of []interface{} as input. Here is more convenient version for go>=1.8:

func Shuffle(slice interface{}) {
    rv := reflect.ValueOf(slice)
    swap := reflect.Swapper(slice)
    length := rv.Len()
    for i := length - 1; i > 0; i-- {
            j := rand.Intn(i + 1)
            swap(i, j)
    }
}

Example usage:

    rand.Seed(time.Now().UnixNano()) // do it once during app initialization
    s := []int{1, 2, 3, 4, 5}
    Shuffle(s)
    fmt.Println(s) // Example output: [4 3 2 1 5]

And also, don't forget that a little copying is better than a little dependency

huangapple
  • 本文由 发表于 2012年9月4日 21:42:28
  • 转载请务必保留本文链接:https://go.coder-hub.com/12264789.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定