Я перетасовываю массив из 3 int, 6 миллионов раз. Я веду подсчет каждой перестановки массива на карте. Код ниже использует go.
package main
import (
"fmt"
"math/rand"
"time"
)
func randRange(min, max int) int {
return rand.Intn(max-min+1) + min
}
func NaiveShuffle(arr *[3]int) {
for i := 0; i < 3; i++ {
e := randRange(0, 2)
arr[e], arr[i] = arr[i], arr[e]
}
}
func main() {
rand.Seed(time.Now().UnixNano())
m := make(map[[3]int]int, 6)
arr := [3]int{-6,10,184}
for i := 1; i <= 6000000; i++ {
a := arr
NaiveShuffle(&arr)
m[a]++
}
for k, v := range m {
fmt.Println(k, ":", v)
}
}
Поскольку я делаю наивную перетасовку, я понимаю, что она не должна давать равномерного распределения перестановок. Но вот что я получаю:
[184 -6 10] : 1000074
[184 10 -6] : 1000764
[-6 10 184] : 1000766
[10 184 -6] : 998090
[-6 184 10] : 1000479
[10 -6 184] : 999827
Это показывает, что каждая из 6 возможных перестановок происходит примерно 1 миллион раз. Почему я получаю то, что кажется равномерным распределением?
Обновлено: изменен код только один раз. Теперь я получаю:
[-6 184 10] : 999507
[184 -6 10] : 1000401
[10 -6 184] : 1002163
[10 184 -6] : 999236
[-6 10 184] : 999016
[184 10 -6] : 999677
EDIT2: благодаря hobbs я понял, что совершил глупую ошибку. Я должен перемешать a
, а не arr
. Теперь я получаю:
[10 -6 184] : 1111056
[-6 10 184] : 888442
[184 -6 10] : 888576
[10 184 -6] : 1109896
[-6 184 10] : 1113148
[184 10 -6] : 888882
На самом деле я пытаюсь создать неравномерное распределение. Между прочим, более простой способ создать равномерное распределение — использовать перетасовку Фишера-Йейтса.
Вы перемешиваете arr
снова и снова более шести миллионов раз, не возвращая его в исходное состояние между перемешиваниями — другими словами, ваши шесть миллионов попыток не являются независимыми. Несмотря на то, что каждое перемешивание имеет неравномерное распределение перестановок, наложение этих перестановок друг на друга шесть миллионов раз приводит к распределению, весьма близкому к равномерному.
Право на. Какую глупую ошибку я совершил.
Даже вы восстанавливаете его в исходное состояние. это не случайное событие:
перечислим все случаи:
m := map[string]int{}
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
for k := 0; k < 3; k++ {
a := []string{"a", "b", "c"}
a[i], a[0] = a[0], a[i]
a[j], a[1] = a[1], a[j]
a[k], a[2] = a[2], a[k]
m[a[0]+a[1]+a[2]]++
fmt.Printf("%v\n", a)
}
}
}
fmt.Printf("%v\n", m)
результат:
map[abc:4 acb:5 bac:5 bca:5 cab:4 cba:4]
есть все 3*3*3
= 27 случаев
но есть только результат C(3,1) = 6
должно быть не равно (4:5)..
Это объясняет, почему это должно быть предвзятое распределение, но не отвечает на вопрос. Мой тест неверен, и я отредактировал свой пост, чтобы объяснить, что я сделал неправильно.
Конечно. Отредактировал код и опубликовал новые результаты. До сих пор смотрит даже на меня.