Shuffle-Array in Go

81

Ich habe versucht, den folgenden Python-Code in Go zu übersetzen

import random

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

Ich fand meine Go-Version jedoch langwierig und umständlich, da es keine Zufallsfunktion gibt und ich Schnittstellen implementieren und Typen konvertieren musste.

Was wäre eine idiomatische Go-Version meines Codes?

Deamon
quelle
2
Diese Frage hat eine shuffle () -Implementierung: Behandlung von Arrays in Go .
Sjoerd

Antworten:

95

Da Ihre Liste nur aus ganzen Zahlen von 1 bis 25 besteht, können Sie Perm verwenden :

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

Beachten Sie, dass die Verwendung einer durch angegebenen Permutation rand.Permeine effektive Möglichkeit ist, ein beliebiges Array zu mischen.

dest := make([]int, len(src))
perm := rand.Perm(len(src))
for i, v := range perm {
    dest[v] = src[i]
}
Denys Séguret
quelle
Ich bin mir nicht sicher, ob sich die Perm-Methode seit dieser Antwort geändert hat, aber sie gibt "eine pseudozufällige Permutation der ganzen Zahlen [0, n)" zurück. In diesem Szenario wäre das Ergebnis eine Permutation von 0 bis 24.
JayJay
1
@ JayJay, deshalb werden die Zahlen erhöht (eine andere Lösung wäre gewesen, nur 0 auf 25 zu ändern).
Denys Séguret
1
Scrollen Sie weiter nach unten, dies wird jetzt in 1.10 unterstützt: stackoverflow.com/a/46185753/474189
Duncan Jones
101

Die Antwort von dystroy ist durchaus vernünftig, aber es ist auch möglich, zu mischen, ohne zusätzliche Scheiben zuzuweisen .

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

Weitere Informationen zum Algorithmus finden Sie in diesem Wikipedia-Artikel . rand.Permverwendet diesen Algorithmus auch intern.

Evan Shaw
quelle
4
Ich nehme an, dies ist die "Inside-Out" -Version im Artikel, und Sie lassen den i!=jScheck aus?
Matt Joiner
Auf der Wikipedia-Seite scheint dies der "moderne Algorithmus" zu sein (erste Variante). Die "Inside-Out" -Version scheint das Ergebnis in einem neuen Array zu speichern, anstatt das Shuffle an Ort und Stelle durchzuführen.
Jochen
45

Seit 1.10 beinhaltet Go eine offizielle Fisher-Yates Shuffle Funktion.

Dokumentation: pkg/math/rand/#Shuffle

math / rand: Shuffle hinzufügen

Shuffle verwendet den Fisher-Yates-Algorithmus.

Da es sich um eine neue API handelt, haben wir die Möglichkeit, eine viel schnellere Int31nImplementierung zu verwenden, bei der eine Teilung größtenteils vermieden wird.

Infolgedessen BenchmarkPerm30ViaShuffleist es etwa 30% schneller als BenchmarkPerm30, obwohl eine separate Initialisierungsschleife erforderlich ist und Funktionsaufrufe zum Austauschen von Elementen verwendet werden.

Siehe auch das Original CL 51891

Erstens, wie von shelll kommentiert :

Vergessen Sie nicht, den Zufall zu setzen, sonst erhalten Sie immer die gleiche Reihenfolge.
Zum Beispielrand.Seed(time.Now().UnixNano()

Beispiel:

words := strings.Fields("ink runs from the corners of my mouth")
rand.Shuffle(len(words), func(i, j int) {
    words[i], words[j] = words[j], words[i]
})
fmt.Println(words)
VonC
quelle
@Delplace Vielen Dank. Ich habe diesen Link in die Antwort aufgenommen.
VonC
3
Vergessen Sie nicht, den Zufall zu setzen, sonst erhalten Sie immer die gleiche Reihenfolge. Zum Beispiel rand.Seed(time.Now().UnixNano()).
Shelll
@shelll Danke. Ich habe Ihren Kommentar zur besseren Sichtbarkeit in die Antwort aufgenommen.
VonC
7

Die Antwort von Evan Shaw hat einen kleinen Fehler. Wenn wir den Slice vom niedrigsten zum höchsten Index durchlaufen, um ein einheitliches (Pseudo-) Zufalls-Shuffle zu erhalten, müssen wir gemäß demselben Artikel eine zufällige Ganzzahl aus dem Intervall [i,n) im Gegensatz zu[0,n+1) auswählen .

Diese Implementierung macht das, was Sie für größere Eingaben benötigen, aber für kleinere Slices führt sie ein ungleichmäßiges Mischen durch.

Um zu nutzen rand.Intn(), können wir tun:

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

nach dem gleichen Algorithmus aus Wikipedia-Artikel.

Gemeinschaft
quelle
Wenn eine Antwort einen Fehler aufweist, bearbeiten Sie die falsche Antwort, anstatt eine weitere Antwort zu schreiben.
Jacob Marble
2

Möglicherweise können Sie auch die folgende Funktion verwenden:

func main() {
   slice := []int{10, 12, 14, 16, 18, 20}
   Shuffle(slice)
   fmt.Println(slice)
}

func Shuffle(slice []int) {
   r := rand.New(rand.NewSource(time.Now().Unix()))
   for n := len(slice); n > 0; n-- {
      randIndex := r.Intn(n)
      slice[n-1], slice[randIndex] = slice[randIndex], slice[n-1]
   }
}
hkucuk
quelle
1

math/randVergessen Sie bei der Verwendung des Pakets nicht, eine Quelle festzulegen

// 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.

Also habe ich eine ShuffleFunktion geschrieben, die dies berücksichtigt:

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]
    }
}

Und um es zu benutzen:

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

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

Wenn Sie es verwenden möchten, finden Sie es hier https://github.com/shomali11/util

Raed Shomali
quelle
1

Raeds Ansatz ist aufgrund seiner []interface{}Eingabe sehr unflexibel . Hier ist eine bequemere Version für 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)
    }
}

Anwendungsbeispiel:

    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]

Und vergessen Sie auch nicht, dass ein bisschen Kopieren besser ist als ein bisschen Abhängigkeit

Joseph Buchma
quelle
1

Verwenden Sie Shuffle () aus der math/randBibliothek.

Hier ist ein Beispiel:

package main

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

func main() {
    words := strings.Fields("ink runs from the corners of my mouth")
    rand.Shuffle(len(words), func(i, j int) {
        words[i], words[j] = words[j], words[i]
    })
    fmt.Println(words)
}

Da es aus der math/randBibliothek stammt, muss es ausgesät werden. Sehen Sie hier für weitere Details.

stwykd
quelle