Перетасовать массив в Go

Я попытался перевести следующий код Python в Go

import random

list = [i for i in range(1, 25)]
random.shuffle(list)
print(list)

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

Что было бы идиоматической версией Go моего кода?

Ответ 1

Поскольку ваш список - это целые числа от 1 до 25, вы можете использовать Perm:

list := rand.Perm(25)
for i, _ := range list {
    list[i]++
}

Обратите внимание, что использование перестановки, заданной rand.Perm, является эффективным способом перетасовки любого массива.

dest := make([]int, len(src))
perm := rand.Perm(len(src))
for i, v := range perm {
    dest[v] = src[i]
}

Ответ 2

ответ dystroy вполне разумен, но также можно перемешать, не выделяя никаких дополнительных фрагментов.

for i := range slice {
    j := rand.Intn(i + 1)
    slice[i], slice[j] = slice[j], slice[i]
}

Подробнее о алгоритме см. эту статью в Википедии. rand.Perm также использует этот алгоритм внутри.

Ответ 3

Ответа на этот вопрос Evan Shaw имеет небольшую ошибку. Если мы перебираем срез с самого низкого индекса на самый высокий, чтобы получить равномерное (псевдо) случайное перемещение, согласно той же статье, мы должны выберите случайное целое из интервала [i,n) в отличие от [0,n+1).

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

Чтобы использовать rand.Intn(), мы можем сделать:

    for i := len(slice) - 1; i > 0; i-- {
        j := rand.Intn(i + 1)
        slice[i], slice[j] = slice[j], slice[i]
    }

по тому же алгоритму из статьи Википедии.

Ответ 4

Go 1.10 может включать официальную функцию Fisher-Yates shuffle.

См. CL 51891:

math/rand: добавить Shuffle

Shuffle использует алгоритм Фишера-Йейта.

Поскольку это новый API, это дает нам возможность чтобы использовать гораздо более быструю реализацию Int31n, которая в основном избегает деления.

В результате BenchmarkPerm30ViaShuffleпримерно на 30% быстрее, чем BenchmarkPerm30, несмотря на то, что требуется отдельный цикл инициализации и используя вызовы функций для замены элементов.

Ответ 5

При использовании пакета math/rand не забудьте установить источник

// Random numbers are generated by a Source. Top-level functions, such as
// Float64 and Int, use a default shared Source that produces a deterministic
// sequence of values each time a program is run. Use the Seed function to
// initialize the default Source if different behavior is required for each run.

Итак, я написал функцию Shuffle, которая учитывает это:

import (
    "math/rand"
)

func Shuffle(array []interface{}, source rand.Source) {
    random := rand.New(source)
    for i := len(array) - 1; i > 0; i-- {
        j := random.Intn(i + 1)
        array[i], array[j] = array[j], array[i]
    }
}

И использовать его:

source := rand.NewSource(time.Now().UnixNano())
array := []interface{}{"a", "b", "c"}

Shuffle(array, source) // [c b a]

Если вы хотите использовать его, вы можете найти его здесь https://github.com/shomali11/util

Ответ 6

Поднятый подход очень негибкий из-за []interface{} в качестве входных данных. Вот более удобная версия для go >= 1.8:

func Shuffle(slice interface{}) {
    rv := reflect.ValueOf(slice)
    swap := reflect.Swapper(slice)
    length := rv.Len()
    for i := length - 1; i > 0; i-- {
            j := rand.Intn(i + 1)
            swap(i, j)
    }
}

Пример использования:

    rand.Seed(time.Now().UnixNano()) // do it once during app initialization
    s := []int{1, 2, 3, 4, 5}
    Shuffle(s)
    fmt.Println(s) // Example output: [4 3 2 1 5]

Кроме того, не забывайте, что небольшое копирование лучше, чем небольшая зависимость