Comment randomiser l'ordre d'environ 20 éléments avec la complexité la plus basse? (générer des permutations aléatoires)
4 Réponses :
Il y a quelques mois, j'ai blogué sur l'obtention d'une permutation aléatoire d'une liste d'entiers. Vous pouvez utiliser cela comme une permutation d'index de l'ensemble contenant vos éléments, puis vous avez ce que vous voulez.
Permutation de liste aléatoire uniformément distribuée dans F # < / fort>
Dans le premier message, j'explore certaines possibilités, et enfin, j'obtiens "une fonction permettant de permuter de manière aléatoire une liste générique avec O (n) complexité", correctement encapsulée pour fonctionner sur des données immuables (c'est-à-dire qu'il est sans effet secondaire) .
Dans le deuxième poste, je le fais distribué uniformément.
Le code est en F #, j'espère que cela ne vous dérange pas!
bonne chance.
EDIT: Je n'ai pas de preuve formelle, mais l'intuition me dit que la complexité d'un tel algorithme ne peut pas être inférieure à celle de O (n) . J'apprécierais vraiment de voir cela fait plus vite!
Toutes les permutations doivent être possibles et réorganiser une matrice dans un dérangement (c'est-à-dire une permutation p pour laquelle p (k)! = K pour tous k ) exige que chaque élément soit visité. Par conséquent o (n) le pire des cas. Ou est-ce toujours pas assez formel?
Aussi o (n) cas moyens par la même preuve, en témoignez-en, depuis IIRC, la proportion de permutations de (1 ... n) qui sont des approches de dérangements 1 / e en tant qu'approbation de l'infini.
Un moyen simple de randomiser la commande consiste à créer une nouvelle liste de la taille correcte (20 dans votre cas), itérer sur la première liste et ajoutez chaque élément dans une position aléatoire à la deuxième liste. Si la position aléatoire est déjà remplie, placez-la dans la position libre suivante.
Je pense que ce pseudocode est correct: éditer: donc il s'avère que cette réponse n'est-ce pas vraiment aussi bon. Ce n'est ni particulièrement rapide ni particulièrement aléatoire. Merci pour vos commentaires. Pour une bonne réponse, faites défiler vers le haut de la page: -)
Dans le pire cas, cet algorithme est O (n ^ 2) (c.-à-d. Si votre générateur de nombres aléatoires indique "1, 1, 1, 1, 1, 1, 1, ...", je vous ai laissé calculer le reste), pas très optimisé.
Mettre les articles dans la prochaine position libre le rend moins aléatoire. Les articles garderont leur commande originale plus que dans un shuffle vraiment aléatoire. Pour résoudre ce problème, vous devriez choisir une nouvelle position au hasard lorsqu'une position est prise, ce qui le rend bien sûr beaucoup plus lentement.
C'est un bon point Guffa. Je ne me suis jamais rendu compte que. Merci. Au moins j'ai appris quelque chose ici :-)
Probablement quelqu'un déjà mis en œuvre le mélange pour vous. Par exemple, dans Python, vous pouvez utiliser aléatoire.shauffe , en C ++ aléatoire_shauffe , et dans php shuffle .
Étonnamment, dans PHP, il s'appelle shuffle :) Je vais mettre à jour ma réponse.
algorithme de shuffle de Knuth est un bon choix.
Eh bien, je suis déçu que c'est la réponse. Puisque vous devez d'abord itération à travers la liste pour le remplir, puis le mélanger (avec un algorithme de certitude), j'aurais pensé qu'il y avait une meilleure solution.
Que voulez-vous dire par la CCA?
Analyse de corrélation canonique?
Plus sur ce FreeBase.com/view/fr/circa
ca. et CCA. sont des abréviations pour vers , bien que circa est uniquement utilisé pour faire référence à des dates: < Un href = "http://fr.wikipedia.org/wiki/circa" rel = "nofollow noreferrer"> en.wikipedia.org/wiki/circa
N'est-ce pas un duplicata d'une question de liste de liste de liste? Stackoverflow.com/Questtions/375351/...