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.

Learn Web Development with Go!

Sign up for my mailing list and I'll send you a FREE sample from my course - Web Development with Go. The sample includes three chapters from the book, and over 2.5 hours of screencasts.

You will also receive notifications when I release new articles, along with other freebies that I only share with my mailing list.

Avatar of Jon Calhoun
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.

Related articles

Spread the word

Did you find this page helpful? Let others know about it!

Vote on Hacker News

Sharing helps me continue to create both free and premium Go resources.

Want to discuss the article?

See something that is wrong, think this article could be improved, or just want to say thanks? I'd love to hear what you have to say!

You can reach me via email or via twitter.

Recent Articles All Articles Mini-Series Tags About Me Go Courses

©2018 Jonathan Calhoun. All rights reserved.