Wie kann man in R neu abtasten, ohne die Permutationen zu wiederholen?

12

Kann ich in R garantieren, dass ich nicht dieselbe Permutation generiere, wenn ich set.seed () setze und dann die Beispielfunktion zum Randomisieren einer Liste verwende?

dh ...

set.seed(25)
limit <- 3
myindex <- seq(0,limit)
for (x in seq(1,factorial(limit))) {
    permutations <- sample(myindex)
    print(permutations)
}

Dies erzeugt

[1] 1 2 0 3
[1] 0 2 1 3
[1] 0 3 2 1
[1] 3 1 2 0
[1] 2 3 0 1
[1] 0 1 3 2

Werden alle gedruckten Permutationen eindeutige Permutationen sein? Oder gibt es aufgrund der Art und Weise, wie dies implementiert wird, eine Chance, dass ich einige Wiederholungen bekomme?

Ich möchte dies garantiert ohne Wiederholungen tun können. Wie würde ich das machen?

(Ich möchte auch vermeiden, eine Funktion wie permn () verwenden zu müssen, die eine sehr mechanistische Methode zum Generieren aller Permutationen hat - sie sieht nicht zufällig aus.)

Nebenbemerkung --- es sieht so aus, als ob dieses Problem O ((n!)!) Ist, wenn ich mich nicht irre.

Mittenchops
quelle
Standardmäßig ist das Argument 'Ersetzen' von 'Beispiel' auf FALSE gesetzt.
Ocram
Danke ocram, aber das funktioniert innerhalb eines bestimmten Beispiels. Das stellt also sicher, dass 0,1,2 und 3 innerhalb einer Ziehung nicht wiederholt werden (also kann ich 0,1,2,2 nicht zeichnen), aber ich weiß nicht, ob dies garantiert, dass die zweite Stichprobe, Ich kann nicht wieder dieselbe Sequenz von 0123 zeichnen. Das ist es, was ich in Bezug auf die Implementierung frage, ob das Setzen des Startwerts einen Einfluss auf diese Wiederholung hat.
Mittenchops
Ja, das habe ich endlich verstanden, als ich die Antworten
gelesen habe ;-)
1
Wenn limit12 überschritten wird, wird Ihnen wahrscheinlich der Arbeitsspeicher ausgehen, wenn R versucht, Speicherplatz für zuzuweisen seq(1,factorial(limit)). (12! Benötigt ungefähr 2 GB, also 13! Benötigt ungefähr 25 GB, 14! Ungefähr 350 GB usw.)
whuber
2
Es gibt eine schnelle, kompakte und elegante Lösung zum Generieren von Zufallssequenzen aller Permutationen von 1: n, vorausgesetzt, Sie können n bequem speichern! ganze Zahlen im Bereich 0: (n!). Es kombiniert die Inversionstabellendarstellung einer Permutation mit der faktoriellen Basisdarstellung von Zahlen.
whuber

Antworten:

9

Die Frage hat viele gültige Interpretationen. Die Kommentare - insbesondere der, der angibt, dass Permutationen von 15 oder mehr Elementen erforderlich sind (15! = 1307674368000 wird groß) - legen nahe, dass eine relativ kleine , ersatzlose Zufallsstichprobe aller n gewünscht wird ! = n * (n-1) (n-2) ... * 2 * 1 Permutationen von 1: n. Wenn dies zutrifft, gibt es (etwas) effiziente Lösungen.

Die folgende Funktion rpermakzeptiert zwei Argumente n(die Größe der zu untersuchenden Permutationen) und m(die Anzahl der zu zeichnenden Permutationen der Größe n). Wenn sich m n nähert oder n! Überschreitet, dauert die Funktion lange und gibt viele NA-Werte zurück: Sie ist für die Verwendung vorgesehen, wenn n relativ groß ist (z. B. 8 oder mehr) und m viel kleiner als n! Ist. Es funktioniert, indem eine Zeichenfolgendarstellung der bisher gefundenen Permutationen zwischengespeichert und dann (zufällig) neue Permutationen generiert werden, bis eine neue gefunden wird. Es nutzt die assoziative Listenindizierungsfunktion von R, um die Liste der zuvor gefundenen Permutationen schnell zu durchsuchen.

rperm <- function(m, size=2) { # Obtain m unique permutations of 1:size

    # Function to obtain a new permutation.
    newperm <- function() {
        count <- 0                # Protects against infinite loops
        repeat {
            # Generate a permutation and check against previous ones.
            p <- sample(1:size)
            hash.p <- paste(p, collapse="")
            if (is.null(cache[[hash.p]])) break

            # Prepare to try again.
            count <- count+1
            if (count > 1000) {   # 1000 is arbitrary; adjust to taste
                p <- NA           # NA indicates a new permutation wasn't found
                hash.p <- ""
                break
            }
        }
        cache[[hash.p]] <<- TRUE  # Update the list of permutations found
        p                         # Return this (new) permutation
    }

    # Obtain m unique permutations.
    cache <- list()
    replicate(m, newperm())  
} # Returns a `size` by `m` matrix; each column is a permutation of 1:size.

Die Art der replicateist , die Permutationen als zurückzukehren Spaltenvektoren; zB gibt die folgenden ein Beispiel in der ursprünglichen Frage, umgesetzt :

> set.seed(17)
> rperm(6, size=4)
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    1    2    4    4    3    4
[2,]    3    4    1    3    1    2
[3,]    4    1    3    2    2    3
[4,]    2    3    2    1    4    1

Die Timings eignen sich hervorragend für kleine bis mittlere Werte von m bis zu etwa 10.000, verschlechtern sich jedoch bei größeren Problemen. Zum Beispiel wurde eine Probe von m = 10.000 Permutationen von n = 1000 Elementen (eine Matrix von 10 Millionen Werten) in 10 Sekunden erhalten; Eine Stichprobe von m = 20.000 Permutationen von n = 20 Elementen benötigte 11 Sekunden, obwohl die Ausgabe (eine Matrix von 400.000 Einträgen) viel kleiner war. Die Berechnung der Stichprobe von m = 100.000 Permutationen von n = 20 Elementen wurde nach 260 Sekunden abgebrochen (ich hatte nicht die Geduld, auf die Fertigstellung zu warten). Dieses Skalierungsproblem scheint mit Skalierungsineffizienzen bei der assoziativen Adressierung von R in Zusammenhang zu stehen. Man kann es umgehen, indem man Samples in Gruppen von beispielsweise 1000 oder so generiert, diese Samples dann zu einem großen Sample kombiniert und Duplikate entfernt.

Bearbeiten

Wir können eine nahezu lineare asymptotische Leistung erzielen, indem wir den Cache in eine Hierarchie von zwei Caches aufteilen, so dass R niemals eine große Liste durchsuchen muss. Erstellen Sie konzeptionell (obwohl nicht wie implementiert) ein Array, das durch die ersten Elemente einer Permutation indiziert ist . Einträge in diesem Array sind Listen aller Permutationen, die diese ersten Elemente gemeinsam nutzen. Um zu überprüfen, ob eine Permutation gesehen wurde, verwenden Sie ihre ersten Elemente, um ihren Eintrag im Cache zu finden, und suchen Sie dann nach dieser Permutation in diesem Eintrag. Wir können wählen , um die erwarteten Größen aller Listen auszugleichen. Die tatsächliche Implementierung verwendet keinkkkkk-fold Array, das in ausreichender Allgemeinheit schwer zu programmieren wäre, aber stattdessen eine andere Liste verwendet.

Hier sind einige verstrichene Zeiten in Sekunden für einen Bereich von Permutationsgrößen und die Anzahl der angeforderten unterschiedlichen Permutationen:

 Number Size=10 Size=15 Size=1000 size=10000 size=100000
     10    0.00    0.00      0.02       0.08        1.03
    100    0.01    0.01      0.07       0.64        8.36
   1000    0.08    0.09      0.68       6.38
  10000    0.83    0.87      7.04      65.74
 100000   11.77   10.51     69.33
1000000  195.5   125.5

(Die anscheinend anomale Beschleunigung von Größe = 10 auf Größe = 15 ist darauf zurückzuführen, dass die erste Ebene des Caches für Größe = 15 größer ist, wodurch die durchschnittliche Anzahl von Einträgen in den Listen der zweiten Ebene verringert wird, wodurch die assoziative Suche von R beschleunigt wird Kosten im RAM, die Ausführung könnte durch Erhöhen der Cache-Größe k.headder oberen Ebene beschleunigt werden . Nur das Erhöhen um 1 (was die Größe der oberen Ebene mit 10 multipliziert) beschleunigte sich beispielsweise rperm(100000, size=10)von 11,77 Sekunden auf 8,72 Sekunden. Erstellen der oberen Ebene Cache 10-mal größer, jedoch keine nennenswerte Verstärkung erzielt, Taktung bei 8,51 Sekunden.)

Mit Ausnahme von 1.000.000 eindeutigen Permutationen von 10 Elementen (ein wesentlicher Teil aller 10! = Etwa 3,63 Millionen solcher Permutationen) wurden praktisch nie Kollisionen festgestellt. In diesem Ausnahmefall gab es 169.301 Kollisionen, aber keine vollständigen Fehler (tatsächlich wurden eine Million eindeutige Permutationen erhalten).

Beachten Sie, dass bei großen Permutationsgrößen (größer als 20 oder so) die Chance, zwei identische Permutationen selbst in einer Probe mit einer Größe von 1.000.000.000 zu erhalten, verschwindend gering ist. Somit ist diese Lösung hauptsächlich in Situationen anwendbar, in denen (a) eine große Anzahl eindeutiger Permutationen von (b) zwischen und oder so Elementen erzeugt werden sollen, aber dennoch (c) wesentlich weniger als allePermutationen sind erforderlich.n=5n=15n!

Arbeitscode folgt.

rperm <- function(m, size=2) { # Obtain m unique permutations of 1:size
    max.failures <- 10

    # Function to index into the upper-level cache.
    prefix <- function(p, k) {    # p is a permutation, k is the prefix size
        sum((p[1:k] - 1) * (size ^ ((1:k)-1))) + 1
    } # Returns a value from 1 through size^k

    # Function to obtain a new permutation.
    newperm <- function() {
        # References cache, k.head, and failures in parent context.
        # Modifies cache and failures.        

        count <- 0                # Protects against infinite loops
        repeat {
            # Generate a permutation and check against previous ones.
            p <- sample(1:size)
            k <- prefix(p, k.head)
            ip <- cache[[k]]
            hash.p <- paste(tail(p,-k.head), collapse="")
            if (is.null(ip[[hash.p]])) break

            # Prepare to try again.
            n.failures <<- n.failures + 1
            count <- count+1
            if (count > max.failures) {  
                p <- NA           # NA indicates a new permutation wasn't found
                hash.p <- ""
                break
            }
        }
        if (count <= max.failures) {
            ip[[hash.p]] <- TRUE      # Update the list of permutations found
            cache[[k]] <<- ip
        }
        p                         # Return this (new) permutation
    }

    # Initialize the cache.
    k.head <- min(size-1, max(1, floor(log(m / log(m)) / log(size))))
    cache <- as.list(1:(size^k.head))
    for (i in 1:(size^k.head)) cache[[i]] <- list()

    # Count failures (for benchmarking and error checking).
    n.failures <- 0

    # Obtain (up to) m unique permutations.
    s <- replicate(m, newperm())
    s[is.na(s)] <- NULL
    list(failures=n.failures, sample=matrix(unlist(s), ncol=size))
} # Returns an m by size matrix; each row is a permutation of 1:size.
whuber
quelle
Dies ist nah, aber ich stelle fest, dass ich einige Fehler erhalte, wie 1, 2 und 4, aber ich denke, ich verstehe, was Sie meinen, und sollte in der Lage sein, damit zu arbeiten. Vielen Dank! > rperm(6,3) $failures [1] 9 $sample [,1] [,2] [,3] [1,] 3 1 3 [2,] 2 2 1 [3,] 1 3 2 [4,] 1 2 2 [5,] 3 3 1 [6,] 2 1 3
Mittenchops
3

Mit uniquein der richtigen Weise sollte den Trick tun:

set.seed(2)
limit <- 3
myindex <- seq(0,limit)

endDim<-factorial(limit)
permutations<-sample(myindex)

while(is.null(dim(unique(permutations))) || dim(unique(permutations))[1]!=endDim) {
    permutations <- rbind(permutations,sample(myindex))
}
# Resulting permutations:
unique(permutations)

# Compare to
set.seed(2)
permutations<-sample(myindex)
for(i in 1:endDim)
{
permutations<-rbind(permutations,sample(myindex))
}
permutations
# which contains the same permutation twice
MånsT
quelle
Entschuldigung, dass Sie den Code nicht richtig erklärt haben. Ich bin jetzt in Eile, aber ich beantworte gerne alle Fragen, die Sie später haben. Ich habe auch keine Ahnung von der Geschwindigkeit des obigen Codes ...
MånsT
1
Ich habe das, was Sie mir gegeben haben, folgendermaßen funktionalisiert: `myperm <- function (limit) {myindex <- seq (0, limit) endDim <-Faktor (limit) permutations <-sample (myindex) while (is.null (dim (unique) (permutations))) || dim (unique (permutations)) [1]! = endDim) {permutations <- rbind (permutations, sample (myindex))} return (unique (permutations))} 'Es funktioniert, aber während ich kann Limit = 6, Limit = 7 macht meinen Computer überhitzt. = PI denke, es muss noch eine Möglichkeit geben, dies zu
unterproben
@Mittenchops, warum müssen wir Unique für das Resampling in R verwenden, ohne die Permutationen zu wiederholen? Vielen Dank.
Frank
2

I "gehen m zur Seite Schritt Ihre erste Frage ein wenig, und deuten darauf hin , dass , wenn Ihr mit relativ kurzen Vektoren zu tun haben , Sie einfach alle Permutationen erzeugen könnte permnund sie nach dem Zufall bestellen diejenigen mit sample:

x <- combinat:::permn(1:3)
> x[sample(factorial(3),factorial(3),replace = FALSE)]
[[1]]
[1] 1 2 3

[[2]]
[1] 3 2 1

[[3]]
[1] 3 1 2

[[4]]
[1] 2 1 3

[[5]]
[1] 2 3 1

[[6]]
[1] 1 3 2
Joran
quelle
Ich mag das sehr, und ich bin sicher, es ist das richtige Denken. Aber mein Problem ist, dass ich eine Sequenz bis zu 10 verwende. Permn () war zwischen Fakultät (7) und Fakultät (8) signifikant langsamer, daher denke ich, dass 9 und 10 unerschwinglich groß sein werden.
Mittenchops
@Mittenchops Stimmt, aber es ist immer noch möglich, dass Sie sie wirklich nur einmal berechnen müssen, oder? Speichern Sie sie in einer Datei und laden Sie sie dann, wenn Sie sie benötigen, und "probieren" Sie aus der vordefinierten Liste. Sie können also die langsame Berechnung von permn(10)oder was auch immer nur einmal durchführen.
Joran
Richtig, aber wenn ich alle Permutationen irgendwo speichere, bricht auch dies um etwa Fakultät (15) zusammen - einfach zu viel Platz zum Speichern. Aus diesem Grund frage ich mich, ob ich durch Setzen des Seeds Permutationen gemeinsam abtasten kann - und wenn nicht, ob es dafür einen Algorithmus gibt.
Mittenchops
@Mittenchops Das Festlegen eines Startwerts hat keinen Einfluss auf die Leistung. Es garantiert nur den gleichen Start jedes Mal, wenn Sie PRNG anrufen.
Roman Luštrik
1
@Mitten In der Hilfe finden set.seedSie Informationen dazu, wie Sie den Status des RNG speichern und später wiederherstellen können.
whuber