Algorithm to randomize output order of a short array in Go

Question

The key difference between this question and the lots of duplicated answers is that, the input array is short, only 3 elements. --

Say I have an ordered set of int. The size of array is only 3 (or a bit more). I need to randomize their order and return a new array. Although it is a pure algorithm question, but the prefered answer language is in Go.

With Python, How can I output a list in random order?, the answer is random.shuffle.
With Go, https://yourbasic.org/golang/shuffle-slice-array/, the answer should be rand.Shuffle.

However, this is my code:

https://go.dev/play/p/CVu8_Q96-9F

func randShuffle(a []int) {
    rand.Seed(time.Now().UnixNano())
    rand.Shuffle(len(a), func(i, j int) { a[i], a[j] = a[j], a[i] })
}

And this is one of my test run result:

[2 1 3]
[1 3 2]
[2 1 3]
[2 1 3]
[1 3 2]
[1 2 3]
[2 3 1]

which doesn't seems to be very randomized.

Any good idea to have a better randomization for a short 3-elements array?

BTW,

How to output array elements in random order using VHDL says to use a linear feedback shift register, but I don't think it'd be a good idea for this question.
The How to randomize (shuffle) a JavaScript array? gives a Durstenfeld shuffle algorithm, an optimized version of Fisher-Yates. But I presume that its result will be quite similiar to Go's rand.Shuffle. Is it?

it won't "look" random because there are only three elements. rand.Shuffle uses the Fisher-Yates algorithm under the hood. if you implement that on your own, you will see similar results. — skeeter, Mar 30 '23 at 14:16
Here's the implementation of `math.rand.Shuffle`, which does say that it uses Fisher-Yates: https://github.com/golang/go/blob/master/src/math/rand/rand.go#L244-L267 — Solomon Ucko, Mar 30 '23 at 14:19
_"which doesn't seems to be very randomized"_ -- how are you determining that? random doesn't mean evenly distributed, it means random which the output fits just fine. If you want to measure it run it a a million times and plot the histogram. — JimB, Mar 30 '23 at 14:29
Try running it a lot of times and count how many times each permutation occurs. — Solomon Ucko, Mar 30 '23 at 14:29
Ask yourself: how man different permutations of 1, 2, 3 are there? Write them down all. Select one of these permutations randomly (no need to shuffle). — Volker, Mar 30 '23 at 15:09

score 1 · Accepted Answer · answered Mar 31 '23 at 21:11

Move random.Seed from your shuffle function to the main. Seeding of a PRNG should only be done once per program, the successful mimicry of randomness is done by the state transitions of the generator rather than by the seed. Don't re-seed unless you really understand how PRNGs work and are trying to explicitly control the process for reasons such as reproducibility.

The following straightforward modification of your code should meet your needs:

package main

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

func main() {
    rand.Seed(time.Now().UnixNano())

    a := []int{1, 2, 3}
    for i := 0; i < 10; i++ {
        randShuffle(a)
        fmt.Println(a)
    }
}

func randShuffle(a []int) {
    rand.Shuffle(len(a), func(i, j int) { a[i], a[j] = a[j], a[i] })
}

This produces results such as:

[2 3 1]
[3 1 2]
[2 1 3]
[2 3 1]
[1 2 3]
[1 3 2]
[1 2 3]
[3 1 2]
[3 2 1]
[2 3 1]

BINGO! Thanks for spotting the tiny detail that others failed to have identified! — xpt, Apr 03 '23 at 14:56

Algorithm to randomize output order of a short array in Go

1 Answers1