Comment rééchantillonner en R sans répéter les permutations?

12

Dans R, si je mets set.seed (), puis utilise l'exemple de fonction pour randomiser une liste, puis-je garantir que je ne générerai pas la même permutation?

c'est à dire...

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

Cela produit

[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

toutes les permutations imprimées seront-elles des permutations uniques? Ou y a-t-il une chance, selon la façon dont cela est mis en œuvre, que je puisse obtenir des répétitions?

Je veux pouvoir le faire sans répétitions, c'est garanti. Comment ferais-je ça?

(Je veux également éviter d'avoir à utiliser une fonction comme permn (), qui a une méthode très mécaniste pour générer toutes les permutations --- elle n'a pas l'air aléatoire.)

Aussi, sidenote --- il semble que ce problème soit O ((n!)!), Si je ne me trompe pas.

Mittenchops
la source
Par défaut, l'argument 'replace' de 'sample' est défini sur FALSE.
ocram
Merci ocram, mais cela fonctionne avec un échantillon particulier. Donc, cela garantit que 0,1,2 et 3 ne se répéteront pas dans un tirage (donc je ne peux pas dessiner 0,1,2,2), mais je ne sais pas si cela garantit que le deuxième échantillon, Je ne peux plus dessiner la même séquence de 0123. C'est ce que je me demande au niveau de la mise en œuvre, si la définition de la graine a un effet sur cette répétition.
Mittenchops
Oui, c'est ce que j'ai finalement compris en lisant les réponses ;-)
ocram
1
Si limitdépasse 12, vous manquerez probablement de RAM lorsque R tentera d'allouer de l'espace pour seq(1,factorial(limit)). (12! Nécessite environ 2 Go, donc 13!
Aura
2
Il existe une solution rapide, compacte et élégante pour générer des séquences aléatoires de toutes les permutations de 1: n, à condition que vous puissiez stocker confortablement n! entiers compris dans l'intervalle 0: (n!). Il combine la représentation de la table d'inversion d'une permutation avec la représentation de base factorielle des nombres.
whuber

Réponses:

9

La question a de nombreuses interprétations valables. Les commentaires - en particulier celui indiquant que des permutations de 15 éléments ou plus sont nécessaires (15! = 1307674368000 grossit) - suggèrent que ce qu'il faut, c'est un échantillon aléatoire relativement petit , sans remplacement, de tous les n! = n * (n-1) (n-2) ... * 2 * 1 permutations de 1: n. Si cela est vrai, il existe des solutions (quelque peu) efficaces.

La fonction suivante,, rpermaccepte deux arguments n(la taille des permutations à échantillonner) et m(le nombre de permutations de taille n à dessiner). Si m s'approche ou dépasse n !, la fonction prendra du temps et renverra de nombreuses valeurs NA: elle est destinée à être utilisée lorsque n est relativement grand (disons, 8 ou plus) et m est beaucoup plus petit que n !. Il fonctionne en mettant en cache une représentation sous forme de chaîne des permutations trouvées jusqu'à présent, puis en générant de nouvelles permutations (au hasard) jusqu'à ce qu'une nouvelle soit trouvée. Il exploite la capacité d'indexation de liste associative de R pour rechercher rapidement la liste des permutations précédemment trouvées.

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.

La nature de replicateest de renvoyer les permutations sous forme de vecteurs de colonne ; Par exemple , ce qui suit reproduit un exemple dans la question d'origine, transposé :

> 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

Les délais sont excellents pour les valeurs de m petites à modérées, jusqu'à environ 10 000, mais se dégradent pour les problèmes plus importants. Par exemple, un échantillon de m = 10 000 permutations de n = 1 000 éléments (une matrice de 10 millions de valeurs) a été obtenu en 10 secondes; un échantillon de m = 20 000 permutations de n = 20 éléments a nécessité 11 secondes, même si la sortie (une matrice de 400 000 entrées) était beaucoup plus petite; et le calcul de l'échantillon de m = 100 000 permutations de n = 20 éléments a été abandonné après 260 secondes (je n'ai pas eu la patience d'attendre la fin). Ce problème de mise à l'échelle semble être lié à des inefficacités de mise à l'échelle dans l'adressage associatif de R. On peut contourner ce problème en générant des échantillons en groupes de, disons, 1000 environ, puis en combinant ces échantillons en un grand échantillon et en supprimant les doublons.

Éditer

Nous pouvons obtenir des performances asymptotiques presque linéaires en divisant le cache en une hiérarchie de deux caches, de sorte que R n'a jamais à parcourir une grande liste. Conceptuellement (mais pas tel qu'implémenté), créez un tableau indexé par les premiers éléments d'une permutation. Les entrées de ce tableau sont des listes de toutes les permutations partageant ces premiers éléments. Pour vérifier si une permutation a été vue, utilisez ses premiers éléments pour trouver son entrée dans le cache, puis recherchez cette permutation dans cette entrée. Nous pouvons choisir pour équilibrer les tailles attendues de toutes les listes. L'implémentation réelle n'utilise pas dek k k kkkkkk-fold array, qui serait difficile à programmer en généralité suffisante, mais utilise à la place une autre liste.

Voici quelques temps écoulés en secondes pour une plage de tailles de permutation et de nombres de permutations distinctes demandées:

 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

(L'accélération apparemment anormale de size = 10 à size = 15 est due au fait que le premier niveau du cache est plus grand pour size = 15, ce qui réduit le nombre moyen d'entrées dans les listes de second niveau, accélérant ainsi la recherche associative de R.. coût en RAM, l'exécution pourrait être accélérée en augmentant la taille du cache de niveau supérieur. Une simple augmentation k.headde 1 (qui multiplie la taille de niveau supérieur par 10) passait rperm(100000, size=10)de 11,77 secondes à 8,72 secondes, par exemple. Faire le niveau supérieur cache 10 fois plus grand mais sans gain appréciable, cadencé à 8,51 secondes.)

À l'exception du cas de 1 000 000 de permutations uniques de 10 éléments (une partie substantielle des 10! = Environ 3,63 millions de ces permutations), pratiquement aucune collision n'a été détectée. Dans ce cas exceptionnel, il y a eu 169 301 collisions, mais aucune défaillance complète (un million de permutations uniques ont en fait été obtenues).

Notez qu'avec de grandes tailles de permutation (supérieures à 20 environ), la chance d'obtenir deux permutations identiques, même dans un échantillon de 1 000 000 000, est extrêmement faible. Ainsi, cette solution est applicable principalement dans les situations où (a) un grand nombre de permutations uniques de (b) entre et environ éléments doivent être générés mais même ainsi, (c) sensiblement moins que tous lesdes permutations sont nécessaires.n = 15 n !n=5n=15n!

Le code de travail suit.

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
la source
C'est proche, mais je remarque que je reçois des erreurs, comme 1, 2 et 4, mais je pense que je vois ce que vous voulez dire et que vous devriez pouvoir travailler avec. Merci! > 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

Utiliser uniquede la bonne manière devrait faire l'affaire:

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
la source
Désolé de ne pas expliquer le code correctement. Je suis un peu pressé maintenant, mais je suis heureux de répondre à vos questions plus tard. De plus, je n'ai aucune idée de la vitesse du code ci-dessus ...
MånsT
1
J'ai fonctionnalisé ce que vous m'avez donné de cette façon: `myperm <- function (limit) {myindex <- seq (0, limit) endDim <-factorial (limit) permutations <-sample (myindex) while (is.null (dim (unique (unique) (permutations))) || dim (unique (permutations)) [1]! = endDim) {permutations <- rbind (permutations, sample (myindex))} return (unique (permutations))} 'Cela fonctionne, mais pendant que je peut faire limit = 6, limit = 7 fait surchauffer mon ordinateur. = PI pense qu'il doit encore y avoir un moyen de sous-échantillonner cela ...
Mittenchops
@Mittenchops, pourquoi dites-vous que nous devons utiliser unique pour rééchantillonner en R sans répéter les permutations? Je vous remercie.
Frank
2

Je vais passer un peu à côté de votre première question, et suggérer que si vous avez affaire à des vecteurs relativement courts, vous pouvez simplement générer toutes les permutations en utilisant permnet les ordonner au hasard celles en utilisant 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
la source
J'aime beaucoup ça, et je suis sûr que c'est la bonne pensée. Mais mon problème me fait utiliser une séquence allant jusqu'à 10. Permn () était significativement plus lent entre factorielle (7) et factorielle (8), donc je pense que 9 et 10 vont être énormément énormes.
Mittenchops
@Mittenchops C'est vrai, mais il est toujours possible que vous n'ayez vraiment besoin de les calculer qu'une seule fois, non? Enregistrez-les dans un fichier, puis chargez-les lorsque vous en avez besoin et "échantillonnez" à partir d'une liste prédéfinie. Ainsi, vous pouvez faire le calcul lent permn(10)ou autre une seule fois.
joran
D'accord, mais si je stocke toutes les permutations quelque part, même cela se décompose d'environ factoriel (15) --- tout simplement trop de place pour stocker. C'est pourquoi je me demande si la définition de la graine me permettra d'échantillonner collectivement les permutations --- et sinon, s'il existe un algorithme pour le faire.
Mittenchops
@Mittenchops La définition d'une valeur de départ n'influencera pas les performances, elle garantit simplement le même démarrage à chaque fois que vous appelez PRNG.
Roman Luštrik
1
@Mitten Voir l'aide pour set.seed: il décrit comment enregistrer l'état du RNG et le restaurer plus tard.
whuber