›

Mélange tableau

lugdanumlugdanum Membre
12:07 modifié dans API UIKit #1
Bonsoir

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.

Réponses

  • muqaddarmuqaddar Administrateur
    12:07 modifié #2
    Avec des randoms :
    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...
  • Philippe49Philippe49 Membre
    juin 2009 modifié #3
    Schlum avait aussi présenté un algorithme de dérangement particulièrement simple. En gros,
    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 ...


  • AliGatorAliGator Membre, Modérateur
    12:07 modifié #4
    Une autre solution si tu as un NSArray (et pas un tableau C) c'est d'utiliser sortUsingDescriptor (ou sortUsingFunction ou ce genre) en passant un descriptor/une méthode/une fonction qui retourne NSOrderAscending/NSOrderDescending de façon aléatoire (au lieu de comparer les 2 opérandes pour dire qui est le plus petit et qui est le plus grand).
  • schlumschlum Membre
    juin 2009 modifié #5
    dans 1244527539:

    Schlum avait aussi présenté un algorithme de dérangement particulièrement simple. En gros,
    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...)
  • CéroceCéroce Membre, Modérateur
    12:07 modifié #6
    dans 1244533192:

    Une autre solution si tu as un NSArray (et pas un tableau C) c'est d'utiliser sortUsingDescriptor (ou sortUsingFunction ou ce genre) en passant un descriptor/une méthode/une fonction qui retourne NSOrderAscending/NSOrderDescending de façon aléatoire


    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.
  • Philippe49Philippe49 Membre
    juin 2009 modifié #7
    dans 1244537439:

    dans 1244527539:

    Schlum avait aussi présenté un algorithme de dérangement particulièrement simple. En gros,
    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...)


    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. 
  • AliGatorAliGator Membre, Modérateur
    12:07 modifié #8
    dans 1244539749:

    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.
    Non pas essayé, et c'est vrai que y'a un risque de bouclage et de foirage de la condition d'arrêt selon comment est implémenté le tri en Cocoa... donc en effet, dangereux en y repensant...
  • schlumschlum Membre
    12:07 modifié #9
    dans 1244539820:

    dans 1244537439:

    dans 1244527539:

    Schlum avait aussi présenté un algorithme de dérangement particulièrement simple. En gros,
    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...)


    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) !
  • schlumschlum Membre
    juin 2009 modifié #10
    dans 1244544883:

    dans 1244539749:

    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.
    Non pas essayé, et c'est vrai que y'a un risque de bouclage et de foirage de la condition d'arrêt selon comment est implémenté le tri en Cocoa... donc en effet, dangereux en y repensant...


    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.
  • Philippe49Philippe49 Membre
    12:07 modifié #11
    Si on accepte des points fixes dans la permutation, il suffit d'ajuster l'algorithme récursif (et l'écrire éventuellement en boucle) :
    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.
  • schlumschlum Membre
    juin 2009 modifié #12
    Ou plus simplement ce que j'ai mis au dessus, ça fait 3 fois moins de permutations  :P (ne permuter que si indice random différent de i).

    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...).
  • Philippe49Philippe49 Membre
    juin 2009 modifié #13
    dans 1244556044:

    Ou plus simplement ce que j'ai mis au dessus, ça fait 3 fois moins de permutations   (ne permuter que si indice random différent de i).

    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

    dans 1244556044:

    Oui, il y a parfaite équiprobabilité du fait de la symétrie de l'algorithme.

    Voilà  une affirmation bien imprudente.

    dans 1244556044:

    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...).

    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.
  • schlumschlum Membre
    12:07 modifié #14
    dans 1244558494:

    dans 1244556044:

    Ou plus simplement ce que j'ai mis au dessus, ça fait 3 fois moins de permutations   (ne permuter que si indice random différent de i).

    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


    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

    dans 1244556044:

    Oui, il y a parfaite équiprobabilité du fait de la symétrie de l'algorithme.

    Voilà  une affirmation bien imprudente.


    Absolument pas, l'algorithme revient à  faire un tirage équiprobable et placer un élément, puis nouveau tirage équiprobable dans le reste et placement etc.  ;)

    dans 1244556044:

    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...).

    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 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 !
  • Philippe49Philippe49 Membre
    12:07 modifié #15
    dans 1244560615:

    Ben non, tu fais 3 permutations quand j'en fais une + un test  ;)

    Où vois-tu 3 permutations ? je fais un échange comme toi.


    dans 1244556044:


    Oui, il y a parfaite équiprobabilité du fait de la symétrie de l'algorithme.
    Voilà  une affirmation bien imprudente.

    Absolument pas, l'algorithme revient à  faire un tirage équiprobable et placer un élément, puis nouveau tirage équiprobable dans le reste et placement etc.  ;)

    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.

    dans 1244556044:

    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 !

    Ok j'avais lu trop vite.
  • lugdanumlugdanum Membre
    12:07 modifié #16
    Ou là , je vous remercie beaucoup pour vos réponses, mais je ne suis pas assez calé comme vous pour comprendre... Ceci dit c'est très intéressant comme conversation !

    Est-ce que un truc du genre :
    <br />const int N = 8;<br />int A&#91;] = {1, 2, 3, 4, 5, 6, 7, 8};<br />random_shuffle(A, A + N);<br />copy(A, A + N, ostream_iterator&lt;int&gt;(cout, &quot; &quot;));<br />// The printed result might be 7 1 6 3 2 5 4 8, <br />//&nbsp; or any of 40,319 other possibilities.<br />

    (http://www.sgi.com/tech/stl/random_shuffle.html)

    Pourrait fonctionner en l'adaptant ?

    Merci
  • Philippe49Philippe49 Membre
    12:07 modifié #17
    random_shuffle n'est pas dans la bibliothèque standard.
    Tu fais une simple fonction selon l'un des deux algorithmes 1 ou 2 peu importe
  • Philippe49Philippe49 Membre
    12:07 modifié #18
    Au passage, à  ce sujet voir l'algorithme random shuffle
  • schlumschlum Membre
    12:07 modifié #19
    dans 1244563692:

    dans 1244560615:

    Ben non, tu fais 3 permutations quand j'en fais une + un test  ;)

    Où vois-tu 3 permutations ? je fais un échange comme toi.


    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...).

    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.


    Voui, enfin là  ce sont des probas plutôt simples :)
    ça revient à  un tirage du loto... Heureusement que toutes les possibilités sont équiprobables !
  • schlumschlum Membre
    12:07 modifié #20
    dans 1244572600:

    Au passage, à  ce sujet voir l'algorithme random shuffle


    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...)
  • AliGatorAliGator Membre, Modérateur
    12:07 modifié #21
    A propos d'optimiser les cas et de savoir s'il faut faire un test ou pas avant l'affectation, et comment implémenter le swap et tout... J'ai jamais trop regardé mais il me semble qu'il existe des fonctions atomiques qui font ce genre d'opérations en utilisant des instructions processeur directement, genre OSAtomicCompareAndSwap32 ou je sais plus quoi, non ?
  • schlumschlum Membre
    12:07 modifié #22
    Le problème c'est que le test est sur l'indice et le swap sur les valeurs...
    Je ne sais pas trop comment fonctionne ta fonction :
    OSAtomicCompareAndSwap32(int32_t oldValue, int32_t newValue, volatile int32_t *theValue);
Connectez-vous ou Inscrivez-vous pour répondre.