shuffle array in 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?

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.

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]
}

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)

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.

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]
   }
}

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.

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

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