Эффективный алгоритм перетасовки Кнута

алгоритм

Сегодня столкнулся с проблемой при составлении игрового требования.Задача очень простая.Дано 75 шаров,пронумерованных 1-75,нужно сделать так,чтобы позиция была случайной при инициализации.

Очевидно, мы можем инициализировать массив A, поместить в него 75 чисел, а затем выполнить функцию перемешивания, чтобы случайным образом поменять местами элементы, чтобы он был случайным.

Я собираюсь сделать перетасовку, но в то же время я хочу посмотреть, есть ли такой интерфейс в golang, чтобы получить результат напрямую.После прочтения это действительно так.Эта функция rand.Perm(n), и эта функция вернет массив.Например, если я передам Enter 75, она вернет случайный массив 0-74.

arr := rand.Perm(75)

Любопытство заставило меня узнать, как в golang реализованы пермские функции?

Откройте исходный код golang и найдите эту функцию в файле rand.go:

// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
func (r *Rand) Perm(n int) []int {
    m := make([]int, n)
    // In the following loop, the iteration when i=0 always swaps m[0] with m[0].
    // A change to remove this useless iteration is to assign 1 to i in the init
    // statement. But Perm also effects r. Making this change will affect
    // the final state of r. So this change can't be made for compatibility
    // reasons for Go 1.
    for i := 0; i < n; i++ {
        j := r.Intn(i + 1)
        m[i] = m[j]
        m[j] = i
    }
    return m
}

Реализация очень простая, но на первый взгляд немного запутанная, т.к. тасовка не используется, а дело решается за один обход.Что происходит?

После тщательного анализа обнаруживается, что этот алгоритм очень деликатный: при каждом обходе текущее число i заменяется случайным числом m[j], уже находящимся в массиве, и, наконец, достигается эффект справедливой рандомизации всего массива. Хотя там всего 3 строчки кода, это шокирует.

Внезапно я чувствую, что golang очень NB и действительно очень эффективен.

Вышеприведенный код имеет 4 строки комментариев, что, вероятно, означает, что нельзя опустить время 0. Это кажется бесполезным, но для того, чтобы позаботиться о случайной последовательности в машине случайных чисел r, его следует добавить, иначе это может привести к отрицательному результату. эффекты. , который связан со случайным начальным числом и последующими случайными последовательностями. Чтобы обеспечить справедливость, не влияя на случайную последовательность, 0 не может быть опущен.

Я поискал в интернете эффективный алгоритм перетасовки и обнаружил, что в питоне тоже есть такая функция, которая пишется вот так:

for(int i = N - 1; i >= 0 ; i -- )
    swap(arr[i], arr[rand(0, i)])         // rand(0, i) 生成 [0, i] 之间的随机整数

И источник этого алгоритма на самом деле исходит от TAOCP! Алгоритм представляет собой знаменитый Knuth-Shuffle, то есть алгоритм перетасовки Кнута.

Казалось бы, простой вопрос даже снова вызвал Кнута, и я потерял дар речи.

Художником можно назвать человека, который может сделать маленькое дело до крайности. Кнут оправдывает свое название.

Наконец, я разделяю слова Кнута:

A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better. Donald E. Knuth 1978

Подпишитесь на официальный аккаунт «ACM Algorithm Daily», чтобы получать больше статей~

Категории