Mélange tableau
Bonsoir
J'ai besoin de vos lumières si vous le permettez ;-)
J'ai in tableau de ce style :
J'aimerais pouvoir le mélanger (comme le permet la commande shuffle en c ?) mais je n'y arrive pas.
En fait quelle est selon vous la meilleure façon de tirer des chiffres au hasard compris dans une plage sans doublon ?
J'ai pensé initialiser un tableau avec des valeurs et ensuite le mélanger ?
Merci d'avances pour vos réponses.
J'ai besoin de vos lumières si vous le permettez ;-)
J'ai in tableau de ce style :
<br />numbers[0] = 10;<br />numbers[1] = 12;<br />numbers[2] = 20;<br />numbers[3] = 22;<br />numbers[4] = 30;<br />
J'aimerais pouvoir le mélanger (comme le permet la commande shuffle en c ?) mais je n'y arrive pas.
En fait quelle est selon vous la meilleure façon de tirer des chiffres au hasard compris dans une plage sans doublon ?
J'ai pensé initialiser un tableau avec des valeurs et ensuite le mélanger ?
Merci d'avances pour vos réponses.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
http://www.osx-dev.com/index.php?topic=776.0
Tu peux tirer un index au hasard et enlever le nombre correspondant une fois l'index tiré. Nombre que tu ajoutes à ton nouveau tableau. Tu le fais N fois, jusqu'à que ton premier tableau soit vide.
Il y a peut-être plus simple...
on tire un indice au hasard entre 0 et N-2, on échange tab[indice] avec tab[N-1]Â
on tire un indice au hasard entre 0 et N-3, on échange tab[indice] avec tab[N-2]
etc...
Je dis bien dérangement, c'est-à -dire une permutation sans point fixe.
Pour une permut, adapter ...
Je ne sais plus si je l'ai présenté comme ça, mais si oui, il y a une faille (des positions non atteignables...)
Il faut plutôt :
- Prendre un nombre 'n' au hasard entre 0 et N-1 et si n!=0, permuter les indices 0 et n
- Prendre un nombre 'n' au hasard entre 1 et N-1 et si n!=1, permuter les indices 1 et n
...
- Prendre un nombre 'n' au hasard entre N-2 et N-1 et si n!=N-2, permuter les indices N-1 et N-2
C'est un algorithme en O(n) et donc plus rapide que d'utiliser un "faux tri" -> O(n*log(n))
Par ailleurs, j'ai un doute sur le faux-tri, je ne pense pas que toutes les positions sont atteignables (à étudier...)
L'idée est intéressante. L'as-tu essayée ? On pourrait croire que le tri ne s'arrête jamais avec cette technique.
je ne vois pas la faille dans cet algorithme, étant entendu qu'il réalise un dérangement , c'est à dire une permutation des éléments sans qu'aucun ne reste à sa place :
Il s'agit en fait d'une boucle pour l'algorithme récursif :
Déranger tab[0..N-1]
  -Echanger un des tab[indice], indice entre 0 et N-2, avec tab[N-1]
  -Déranger tab[0..N-2]
fin
Pour un choix de la valeur prise par tab[N-1], on parcourt bien tous les dérangements du début du tableau, l'ancien tab[N-1] ne pouvant être remis à sa place initiale.Â
Oui, c'est bien ce que je dis, toutes les configurations où au moins un des items reste à sa place n'est pas " atteignable "...
Je ne sais pas si ça porte un nom, mais c'est un peu foireux quand même (quand on mélange, il y a en théorie, même une infime chance de retomber exactement sur la même suite) !
Les algorithmes de tris performants ne comparent jamais deux fois les mêmes items (et font un nombre fini de comparaisons)... Donc à priori, pas de bouclage.
Permuter tab[0..N-1]
-Echanger un des tab[indice], indice entre 0 et N-1, avec tab[N-1]
-Permuter tab[0..N-2]
fin
Je n'ai pas vérifié si on a alors l'équiprobabilité d'obtention d'une permutation, mais à priori cela devrait.
Oui, il y a parfaite équiprobabilité du fait de la symétrie de l'algorithme.
Sinon, pour en revenir à la solution "tri", l'algo de permutations sera dans les log2(n) fois plus rapide à priori quand même... (8 fois plus rapide pour un tableau à 256 éléments...).
En moyenne une permutation tirée au hasard possède un point fixe.
Le test est donc plus coûteux car il s'effectue N-1 fois inutilement, ce qui représente N+3*(N-1) instructions au lieu de 3N.
En moyenne, ne pas mettre de test devrait être un gain de 1/4
Voilà une affirmation bien imprudente.
Imagine un dérangement, il faut replacer N individus. Par quel miracle peux-tu faire cela en moins de N actions ?
Je place le dernier élément : il faut bien le placer de toute façon non ?
Je place ensuite le précédent : il faut bien le placer de toute façon non ?
...
Cet algorithme est forcément linéaire.
Ben non, tu fais 3 permutations quand j'en fais une + un test
Et n'exagérons rien... un test est 1000 fois plus rapide qu'une permutation :P
Absolument pas, l'algorithme revient à faire un tirage équiprobable et placer un élément, puis nouveau tirage équiprobable dans le reste et placement etc.
Ben oui, c'est ce que j'ai dit il est linéaire (O(n)) alors qu'un algorithme de tri est en O(n*log(n)), donc log(n) fois plus lent !
Où vois-tu 3 permutations ? je fais un échange comme toi.
C'est pour cela que je disais : "à priori cela devrait"
et qu'avant j'ai mis : ""Je n'ai pas vérifié si on a alors l'équiprobabilité d'obtention d'une permutation" car cela demande une attention toute particulière ce genre d'affirmation, et c'est vraiment le genre de truc dans lequel on a souvent des surprises, crois en un vieux prof de math-spe.
Ok j'avais lu trop vite.
Est-ce que un truc du genre :
(http://www.sgi.com/tech/stl/random_shuffle.html)
Pourrait fonctionner en l'adaptant ?
Merci
Tu fais une simple fonction selon l'un des deux algorithmes 1 ou 2 peu importe
Ah, j'avais pas vu que c'était un truc récursif... C'est le même que le mien, sauf que tu fais l'échange même si les indices sont les mêmes (c'est pour ça que j'avais fait un test pour éviter un swap inutile...).
Voui, enfin là ce sont des probas plutôt simples
ça revient à un tirage du loto... Heureusement que toutes les possibilités sont équiprobables !
C'est encore une fois le même... (sauf qu'ils n'ont pas mis le test, donc si i==k, ils font le swap quand même...)
Je ne sais pas trop comment fonctionne ta fonction :