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.
r
sampling
combinatorics
resampling
Mittenchops
la source
la source
limit
dépasse 12, vous manquerez probablement de RAM lorsque R tentera d'allouer de l'espace pourseq(1,factorial(limit))
. (12! Nécessite environ 2 Go, donc 13!Réponses:
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,,
rperm
accepte deux argumentsn
(la taille des permutations à échantillonner) etm
(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.La nature de
replicate
est de renvoyer les permutations sous forme de vecteurs de colonne ; Par exemple , ce qui suit reproduit un exemple dans la question d'origine, transposé :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 kk k k k k -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:
(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.head
de 1 (qui multiplie la taille de niveau supérieur par 10) passaitrperm(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 = 5 n=15 n!
Le code de travail suit.
la source
> 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
Utiliser
unique
de la bonne manière devrait faire l'affaire:la source
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
permn
et les ordonner au hasard celles en utilisantsample
:la source
permn(10)
ou autre une seule fois.set.seed
: il décrit comment enregistrer l'état du RNG et le restaurer plus tard.