# How to shuffle arrays and slices in Go

If you are transitioning into Go from a language like Python or Ruby, at some point or another you are going to start missing one of the many helper functions offered by the language. The most recent example of this for me was when I wanted to shuffle a slice.

In Ruby this is as simple as calling the `shuffle` method.

``````array = [1, 2, 3, 4, 5]
array.shuffle # shuffles the array!
``````

And Python is just as easy.

``````import random
array = [1, 2, 3, 4, 5]
random.shuffle(array) # shuffles the array!
``````

Unfortunately it is a little trickier in Go, so in this post we are going to explore all of our options. We will start out with a few straight forward approaches that uses slices, but most of these approaches will work on arrays as well.

## The naive approach - creating a new slice or array

The most naive approach is to randomly pick an item from your existing slice, remove it, and then insert it into a new slice. We can use the `math/rand` package’s Intn() method to pick the random element, and we can use append to remove elements from the middle of our slice.

``````func Shuffle(vals []int) []int {
r := rand.New(rand.NewSource(time.Now().Unix()))
ret := make([]int, len(vals))
n := len(vals)
for i := 0; i < n; i++ {
randIndex := r.Intn(len(vals))
ret[i] = vals[randIndex]
vals = append(vals[:randIndex], vals[randIndex+1:]...)
}
return ret
}
``````

`Intn(N)` works by generating a random number between `0` and `N` (but not `N`) and then returning it. We can use this to pick a random element by using it to select a valid index and then getting the element at that index.

Using `append()` to shrink our slice works by taking advantage of variadic parameters, but unfortunately this comes at a cost. Our code could potentially be `O(n^2)` if we always removed the first element in our slice, as it would need to shift every other element left by one position every time we picked a random element. That isn’t very good.

Let’s look at how we can use rand.Perm() to do this a bit more efficiently.

``````func Shuffle(vals []int) []int {
r := rand.New(rand.NewSource(time.Now().Unix()))
ret := make([]int, len(vals))
perm := r.Perm(len(vals))
for i, randIndex := range perm {
ret[i] = vals[randIndex]
}
return ret
}
``````

This works because `rand.Perm()` will return a random permutation of the numbers 0 through N (not including N), so when we call it we don’t get a shuffled array, but we do receive a random list of indexes that we could access.

Unfortunately, both of these approaches require us to create a new slice (or array), and return it. To avoid this, we need to try a slightly different approach.

## Shuffling without creating a new slice or array.

Just like in our last example, we are going to use `rand.Perm()` but this time instead of creating a new slice and returning it we are simply going to use the elements in our slice out of order. This might sound like cheating, and it is virtually identical to what we did in the last `Shuffle()` function, but most of the time this will solve your problem as well as any other approach. As an added bonus, it also leaves your initial slice in its original order.

``````func main() {
vals := []int{10, 12, 14, 16, 18, 20}
r := rand.New(rand.NewSource(time.Now().Unix()))
for _, i := range r.Perm(len(vals)) {
val := vals[i]
fmt.Println(val)
}
}
``````

Now if you really need to shuffle your slice without creating a new one, the best way I have found is to start at one end of the slice or array and insert each “random” number into that location. The code for this is shown below, and once again we utilize `rand.Intn()`.

``````func Shuffle(vals []int) {
r := rand.New(rand.NewSource(time.Now().Unix()))
// We start at the end of the slice, inserting our random
// values one at a time.
for n := len(vals); n > 0; n-- {
randIndex := r.Intn(n)
// We swap the value at index n-1 and the random index
// to move our randomly chosen value to the end of the
// slice, and to move the value that was at n-1 into our
// unshuffled portion of the slice.
vals[n-1], vals[randIndex] = vals[randIndex], vals[n-1]
}
}
``````

You can even leverage the fact that the length and capacity of a slice won’t be altered when you pass a slice by value, meaning you can just as easily truncate the slice instead of keeping track of `n` like we did in our last example. The result of doing this is shown below.

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

I can’t say that I would particularly recommend this approach, but I do find it interesting and worth understanding. If you want to read more about why this works, check out my article Why are slices sometimes altered when passed by value in Go?.

## In conclusion

You might be asking yourself, “Why doesn’t Go just provide a shuffle function?” and you might be right, but even so I do think it is important to have a rough understanding of how to shuffle a slice.

If you have come up with another way to shuffle your slices I would love to hear about it. Written by
Jon Calhoun

Jon Calhoun is a full stack web developer who also teaches about Go, web development, algorithms, and anything programming related. He also consults for other companies who have development needs. (If you need some development work done, get in touch!)

Jon is a co-founder of EasyPost, a shipping API that many fortune 500 companies use to power their shipping infrastructure, and prior to founding EasyPost he worked at google as a software engineer.

Jon's latest progress update: Writing Course Notes

Related articles