Алгоритм рандомизации порядка вывода короткого массива в Go
Ключевое отличие этого вопроса от множества повторяющихся ответов заключается в том, что входной массив короткий, всего 3 элемента. --
Скажем, у меня есть заказанный набор int. Размер массива всего 3 (или чуть больше). Мне нужно рандомизировать их порядок и вернуть новый массив. Хотя это чисто алгоритмический вопрос, но предпочтительным языком ответов является Go.
- С Python, Как я могу вывести список в случайном порядке?, ответ
random.shuffle. - С Go, https://yourbasic.org/golang/shuffle-slice-array/, ответ должен быть
rand.Shuffle.
Однако это мой код:
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] })
}
И это один из результатов моего тестового прогона:
[2 1 3]
[1 3 2]
[2 1 3]
[2 1 3]
[1 3 2]
[1 2 3]
[2 3 1]
который, кажется, не очень рандомизирован.
Любая хорошая идея, чтобы иметь лучшую рандомизацию для короткого массива из 3 элементов?
КСТАТИ,
- Как выводить элементы массива в случайном порядке с помощью VHDL говорит использовать регистр сдвига с линейной обратной связью, но я не думаю, что это будет хорошей идеей для этого вопроса.
- Как рандомизировать (перетасовать) массив JavaScript? дает алгоритм перетасовки Дюрстенфельда, оптимизированную версию алгоритма Фишера-Йейтса. Но я предполагаю, что его результат будет очень похож на
rand.ShuffleGo. Это?
Вот реализация math.rand.Shuffle, в которой говорится, что она использует Fisher-Yates: github.com/golang/go/blob/master/src/math/rand/…
«что не кажется очень рандомизированным» - как вы это определяете? случайный не означает равномерно распределенный, это означает случайный, который отлично подходит для вывода. Если вы хотите измерить его, запустите его миллион раз и постройте гистограмму.
Попробуйте запустить его много раз и посчитайте, сколько раз встречается каждая перестановка.
Спросите себя: сколько существует различных перестановок 1, 2, 3? Запишите их все. Выберите одну из этих перестановок случайным образом (не нужно перемешивать).
Ответы 1
Переместите random.Seed из функции перемешивания в основную. Заполнение PRNG должно выполняться только один раз для каждой программы, успешная имитация случайности выполняется переходами состояний генератора, а не начальным числом. Не выполняйте повторное заполнение, если вы действительно не понимаете, как работают PRNG, и не пытаетесь явно контролировать процесс по таким причинам, как воспроизводимость.
Следующая простая модификация вашего кода должна удовлетворить ваши потребности:
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] })
}
Это дает такие результаты, как:
[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]
БИНГО! Спасибо, что заметили крошечную деталь, которую другие не смогли определить!
это не будет "выглядеть" случайным, потому что есть только три элемента. rand.Shuffle использует алгоритм Фишера-Йейтса под капотом. если вы реализуете это самостоятельно, вы увидите аналогичные результаты.