IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Collection et Stream Java Discussion :

Comment remplir un tableau avec random sans doublon ?


Sujet :

Collection et Stream Java

  1. #1
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Juillet 2010
    Messages
    1
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Juillet 2010
    Messages : 1
    Points : 1
    Points
    1
    Par défaut Comment remplir un tableau avec random sans doublon ?
    Bonjour je suis nouveau en programmation, est ce quelqu'un veut bien m'aider à remplir un tableau avec aléatoirement avec un random sans doublon ? donc si le nombre exite déjà dans mon tableau je l'ignore et je rempli juste avec les nombres générés qui ne se trouve pas encore dans mon tableau.

    Je me suis un peu inspiré de l'exemple de recherche, qui se trouve sur le cours java( site zéro : section tableau ).

    Aidez-moi s'il vous plait, si vous avez une solution plus pratique et plus clair ou encore si vous pouvez m'expliquer qu'est ce qui ne va pas dans mon code et en me proposons une solution.

    Donc voici ce que j'ai fait : malheureusement il m'affiche des zéros partout.

    Merci d'avance.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
     
    for(int i=0; i<tab.length; i++)   // le tableau à 2 dimensions que je dois remplir   
    	{      
    	for(int j=0; j<tab[i].length; j++) {   
    		Random r = new Random();
                    int valeur = 1 + r.nextInt(9);
    	        tab_test[count] = valeur; // je rempli un tableau à 1 dimension pour faire mes tests
    	        count++;
     
    		while((count1 < tab_test.length) && (valeur!= tab_test[count1])){
    		    count1++;
    		    if(count1>tab_test.length) {
    		  	tab[i][j]= valeur; 
    		    }
                     }
           }
    }

  2. #2
    Membre averti
    Profil pro
    Inscrit en
    Avril 2008
    Messages
    342
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2008
    Messages : 342
    Points : 419
    Points
    419
    Par défaut
    tu ne peut pas utiliser des collection de set qui ne vont pas vouloir de doublon ?

  3. #3
    Expert confirmé
    Homme Profil pro
    Inscrit en
    Septembre 2006
    Messages
    2 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Septembre 2006
    Messages : 2 957
    Points : 4 386
    Points
    4 386
    Par défaut
    Citation Envoyé par muntu Voir le message
    Bonjour je suis nouveau en programmation, est ce quelqu'un veut bien m'aider à remplir un tableau avec aléatoirement avec un random sans doublon ? donc si le nombre exite déjà dans mon tableau je l'ignore et je rempli juste avec les nombres générés qui ne se trouve pas encore dans mon tableau.

    Je me suis un peu inspiré de l'exemple de recherche, qui se trouve sur le cours java( site zéro : section tableau ).

    Aidez-moi s'il vous plait, si vous avez une solution plus pratique et plus clair ou encore si vous pouvez m'expliquer qu'est ce qui ne va pas dans mon code et en me proposons une solution.

    Donc voici ce que j'ai fait : malheureusement il m'affiche des zéros partout.

    Merci d'avance.

    for(int i=0; i<tab.length; i++) // le tableau à 2 dimensions que je dois remplir

    {
    for(int j=0; j<tab[i].length; j++)

    {


    Random r = new Random();
    int valeur = 1 + r.nextInt(9);

    tab_test[count] = valeur; // je rempli un tableau à 1 dimension pour faire mes tests

    count++;






    while((count1 < tab_test.length) && (valeur!= tab_test[count1]))

    {
    count1++;

    if(count1>tab_test.length) {

    tab[i][j]= valeur;
    }
    }
    }
    }
    pour être certain de remplir le tableau sans collision il faut commencer par mettre
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    int valeur = 1 + r.nextInt(length*length);


    pour votre problématique, vous pouvez aussi inverser la logique :

    au lieu de parcourir le tableau linéairement et mettre un nombre aléatoire dont vous devez vérifier qu'il n'a pas déjà été utilisé…
    remplissez le tableau en parcourant l'espace des valeurs (dans votre cas [1..length^2]) et ensuite mélangez-le de manière aléatoire…
    au moins le temps d'exécution sera toujours le même puisque vous déciderez une fois pour toute combien d'opérations de mélange (échanges de 2 éléments du tableau, rotations, …) vous effectuerez pour obtenir un "bon" mélange…
    et pour augmenter le caractère aléatoire vous pouvez aussi randomiser la position de départ du remplissage avant mélange…

  4. #4
    Membre habitué
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    173
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 173
    Points : 151
    Points
    151
    Par défaut
    Bonjour,

    Ce bout de code permet de remplir une matrice de taille déterminée de nombres aléatoire de entre -3 et 3

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Random;
     
    public class Main {
     
    	public static void main(String[] args) throws InterruptedException {
     
    		List<List<Integer>> list = new ArrayList<List<Integer>>();
     
    		final int nb = 3; // nb éléments
    		int colone = 0;
    int limite = 10;
    		while (colone < nb) {
    			int ligne = 0;
     
    			List<Integer> listTmp = new ArrayList<Integer>();
    			while (ligne < nb) {
    				Random r = new Random();
    				int nouvelElement = r.nextInt(limite);
     
    				if (!list.contains(nouvelElement)) {
    					listTmp.add(nouvelElement);
    					ligne++;
    				}
     
    			}
    			colone++;
    			list.add(listTmp);
    		}
     
    	}
     
    }
    En Java il est beaucoup plus pratique et conseiller de manipuler des List (ou Collection) plutot que des tab (int[]).

    Dans mon exemple, j'ai défini une matrice comme étant une liste de liste et lu le tableau selon une direction, c'est assez intuitif non?

    J'espère que ce bout de code convient

    N'hésite pas

  5. #5
    Expert confirmé
    Homme Profil pro
    Inscrit en
    Septembre 2006
    Messages
    2 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Septembre 2006
    Messages : 2 957
    Points : 4 386
    Points
    4 386
    Par défaut
    Citation Envoyé par amine_en_france Voir le message
    Bonjour,

    Ce bout de code permet de remplir une matrice de taille déterminée de nombres aléatoire de entre -3 et 3
    ce genre de code n'aucune "scalability"… List.contains est O(n)…

  6. #6
    Membre habitué
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    173
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 173
    Points : 151
    Points
    151
    Par défaut
    Citation Envoyé par JeitEmgie Voir le message
    ce genre de code n'aucune "scalability"… List.contains est O(n)…
    Je ne comprends pas...

  7. #7
    Modérateur

    Profil pro
    Inscrit en
    Septembre 2004
    Messages
    12 564
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2004
    Messages : 12 564
    Points : 21 629
    Points
    21 629
    Par défaut
    Moi non plus. Mélanger au hasard ne peut pas être à la fois bien fait et bien scalable, il me semble.
    Ceci étant dit, ce n'est pas efficace de tourner en boucle jusqu'à tirer au hasard un nombre qui n'est pas déjà pris. Il faut tirer au hasard un nombre parmi ceux qui ne sont pas déjà pris.
    Rien à voir avec la complexité de List.contains(), par contre.

    Et puis bon, au final si c'est pour faire des solutions trop compliquées, autant faire ça tout de suite avec Collections.shuffle().

  8. #8
    Expert confirmé
    Homme Profil pro
    Inscrit en
    Septembre 2006
    Messages
    2 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Septembre 2006
    Messages : 2 957
    Points : 4 386
    Points
    4 386
    Par défaut
    Citation Envoyé par amine_en_france Voir le message
    Je ne comprends pas...
    pour des petites quantités de données, çà ne se voit pas…
    essayer de remplir un tableau important… vous allez vite comprendre…

    non seulement les techniques consistant à garder une trace des nombres déjà utilisés utilisent 2x plus de mémoire (le tableau et la structure)
    mais en plus le code pour tester si le nombre a déjà été utilisé est de plus en plus lent… et de ce point de vue List.contains est bien pire que Hash.get…

    si au moins la structure maintenant les nombres utilisés était un bitset… vous ne consommeriez que (nombre d'éléments / nombre de bits dans un Long)
    et le temps d'exécution du test d'utilisation d'un nombre serait linéaire…

  9. #9
    Membre averti
    Profil pro
    Inscrit en
    Avril 2008
    Messages
    342
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2008
    Messages : 342
    Points : 419
    Points
    419
    Par défaut
    il y a une chose que je ne comprend pas

    tu veut avoir des nombres complètement aléatoire ?
    ou avoir un tableau avec tout les valeurs possible mais non rangé ?

    je m'explique avec un tableau de 4*4

    1762655575 | 761419280 | 1879594817 | 110619298
    1955250789 | 1793058608 | 1931675481 | 87287533
    694153684 | 1690546066 | 1654657149 | 313483780
    1055369960 | 1013363579 | 582852338 | 2089421762
    ou alors.

    8 | 11 | 9 | 13
    7 | 4 | 10 | 15
    3 | 2 | 12 | 1
    6 | 14 | 5 | 16
    car les 2 cas ne ce traite pas pareille pour moi dans le 1er cas je remplirais mon tableau en partent du principe qu'il n'y a pas de doublons et seulement après je remplacerais les valeurs qui sont en double

    dans l'autre cas je remplirais de manière méthodique mon tableau pour le melanger par la suite

  10. #10
    Membre régulier
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    54
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Avril 2010
    Messages : 54
    Points : 74
    Points
    74
    Par défaut
    Citation Envoyé par JeitEmgie Voir le message
    pour des petites quantités de données, çà ne se voit pas…
    essayer de remplir un tableau important… vous allez vite comprendre…

    non seulement les techniques consistant à garder une trace des nombres déjà utilisés utilisent 2x plus de mémoire (le tableau et la structure)
    mais en plus le code pour tester si le nombre a déjà été utilisé est de plus en plus lent… et de ce point de vue List.contains est bien pire que Hash.get…
    Parce que faire un tableau avec toutes les valeurs possible, ça mange pas la mémoire peut-être? Si j'ai besoin de tirer 10 nombres différents parmis une ensemble de 1.000.000 de valeur possible, je n'irais surement pas utiliser un tableau mélangé, qui sera extêmement plus lent et plus consomatteur de mémoire que de tirer et rejeter les nombre non valide.

    De plus, il n'existe pas, à ma connaissance, de règles qui permettent de faire un "mélange" du tableau de façon aléatoire correcte. Pour le tirage en utilisant un tableau, on utilise en général cette technique, qui évite de devoir perdre du temps à mélanger un tableau qui sert au tirage.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    Prendre un tableau de N élément (ils peuvent être rangés, ça n'a pas d'importance)
    Tirer au hasard une valeur i entre 0 et N
    rajouter tableau[i] aux éléments tirés
    mettre le Nième élément de tableau en position i 
    on réduit le tableau de une taille
    si on a pas fini le tirage, on continue avec ce tableau réduit.
    Avec ça, l'occupation mémoire est N,
    le temps de préparation et O(N) (on prépare le tableau au début)
    le temps de tirage est O(X) (X étant le nombre d'éléments à tirer).

    C'est en fait le principe du paquet de carte, sauf qu'au lieu de battre les cartes, on les étale et on en tire au hasard dedans

    En "gros", toutes les réponses de ce thread sont bonnes. Ce qui compte, au départ, c'est de savoir

    -> Quel est la taille de l'ensemble des valeur possible, est-il fini?
    -> Combien de nombres faut-il tirer?

    Si on a un équilibre raisonnable entre le nombre de valeurs possible et le nombre de tirage (exemple: tirer 30% des valeurs possibles) -> on utilise un technique tableau dans la mesure du possible
    Si on a peu de tirage par rapport aux valeur possibles -> on utilise un simple algorithme de tirage / rejet si déjà tiré. Pour le rejet, un tableau trié des valeurs déjà tirées ou l'utilisation d'un SortedSet sont préférable à List pour des raisons de performance.

    Tout est une question de besoin en définitive

  11. #11
    Membre averti
    Profil pro
    Inscrit en
    Avril 2008
    Messages
    342
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2008
    Messages : 342
    Points : 419
    Points
    419
    Par défaut
    a oui j'ai une autre question pourquoi utilise tu un tableau a 2 dimensions ?

    (si tu nous explique ce que tu veut faire on pourras peut être mieux t'aidé)

  12. #12
    Expert confirmé
    Homme Profil pro
    Inscrit en
    Septembre 2006
    Messages
    2 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Septembre 2006
    Messages : 2 957
    Points : 4 386
    Points
    4 386
    Par défaut
    Citation Envoyé par CastorJoyeux Voir le message
    Parce que faire un tableau avec toutes les valeurs possible, ça mange pas la mémoire peut-être?
    à partir du moment où l'auteur de la question demande comment remplir son tableau à 2 dimensions de manière aléatoire, on s'en tient au fait qu'il a besoin de ce tableau sous cette forme dans son programme…

    et on discute de la manière efficace de le remplir… pas de savoir si ce besoin d'un tableau à 2 dimensions est légitime ou non dans le contexte de son code… ce qui ne fait pas partie de l'énoncé de son problème…

    si on commence à détricoter tout… pourquoi pas se demander s'il a réellement besoin d'un ordinateur pour faire ce qu'il fait…


    Citation Envoyé par CastorJoyeux Voir le message
    Si j'ai besoin de tirer 10 nombres différents parmis une ensemble de 1.000.000 de valeur possible, je n'irais surement pas utiliser un tableau mélangé, qui sera extêmement plus lent et plus consomatteur de mémoire que de tirer et rejeter les nombre non valide.
    avec des si…
    restons sur ce qu'on lit dans la question et ce qu'on voit dans le code soumis :
    le code montré est simplement : remplir une matrice NxN avec les nombres de [1..N^2] de manière aléatoire… (et vu qu'il y traîne un 9… N faudrait 3 …)

    et les seules choses à retenir :

    si N peut prendre de (très) grandes valeurs, il faut éviter toute idée faisant intervenir une deuxième structure contenant N^2 élément pour retenir les nombres déjà utilisés…
    mais si N est petit c'est sans doute moins important… (sauf si on fait çà des millions de fois dans le même programme…)
    et que l'idée de remplir le tableau avec les valeurs possibles et de le mélanger est plus censé que de dépendre de la "qualité" du générateur aléatoire… (le "tant que Random() ne renvoie pas un nombre non utilisé" a une durée d'exécution non déterministe…)

    alors que mélanger un tableau contenant N^2 éléments peut se faire facilement en permutant N^2/2 fois des éléments pris au hasard… soit N^2 appels de Random(N^2)… (et la conversion d'un indice de 0 à N^2 en coordonnées (i, j) est triviale…)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
     
    import java.util.Random;
     
    import org.junit.Test;
     
    public class RandomIntMatrix {
    	protected int size ;
    	protected int[] content  ;
     
    	public RandomIntMatrix() {
    		// for JUnit to be quiet...
    	}
     
    	public RandomIntMatrix(int inSize) {
    		this.size = inSize ;
    		this.content = new int[inSize * inSize] ;
     
    		shuffle() ;
    	}
     
    	public void shuffle() {
    		int s2 = this.size * this.size ;
    		Random r = new Random();
    		int start = r.nextInt(s2) ;
    		int value = 1 ;
    		for(int i=start;i<s2;i++, value++)
    			this.content[i] = value ;
    		for(int i=0;i<start;i++, value++)
    			this.content[i] = value ;
     
    		for(int i=0;i<s2/2;i++) {
    			int i1 = r.nextInt(s2) ;
    			int i2 = r.nextInt(s2) ;
     
    			int t = this.content[i1] ; this.content[i1] = this.content[i2] ; this.content[i2] = t ;
    		}		
    	}
     
    	public int get(int row, int col) {
    		return this.content[ (row * this.size) + col ] ;
    	}
     
    	public void set(int row, int col, int value) {
    		this.content[(row * this.size) + col] = value ;
    	}
     
    	private final int SizeToTest = 10 ;
    	private final int TimesToTest = 2 ;
     
    	@Test
    	public final void testMatrix() {
    		RandomIntMatrix m = new RandomIntMatrix(SizeToTest) ;
     
    		for(int k=0;k<TimesToTest;k++) {
     
    			for(int i=0;i<SizeToTest;i++) {
    				for(int j=0;j<SizeToTest;j++)
    					System.out.print(m.get(i, j) + "\t") ;
    				System.out.println();
    			}
     
    			System.out.println();
     
    			m.shuffle();
    		}
    	}
    }

  13. #13
    Membre régulier
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    54
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Avril 2010
    Messages : 54
    Points : 74
    Points
    74
    Par défaut
    Citation Envoyé par JeitEmgie Voir le message
    à partir du moment où l'auteur de la question demande comment remplir son tableau à 2 dimensions de manière aléatoire, on s'en tient au fait qu'il a besoin de ce tableau sous cette forme dans son programme…

    et on discute de la manière efficace de le remplir… pas de savoir si ce besoin d'un tableau à 2 dimensions est légitime ou non dans le contexte de son code… ce qui ne fait pas partie de l'énoncé de son problème…
    relisez mon message, je n'ai jamais prétendu le contraire.

    si on commence à détricoter tout… pourquoi pas se demander s'il a réellement besoin d'un ordinateur pour faire ce qu'il fait…
    J'ai rien détricoté, j'ai précisé que, suivant le besoin derrière (nombre d'élément, epace des éléments à tirer) la solution est différente. L'auteur n'a jamais précisé dans quel domaine il travaille donc on ne peux que donner diverses solution, inutile de s'étriper là dessus.
    De plus, visiblement j'ai mal compris votre message, j'avais compris, créer un tableau de N (N étant l'espace des éléments possible), le mélanger puis au final prendre les X premiers éléments (X étant le nombre d'éléments à tirer). Je n'ai pas vu que vous supposiez X = N comme contrainte de départ.

    Mais mon deuxième argument reste, cependant. Combien de fois mélanger pour avoir une garantie de distribution uniforme? Si je garde le N/2 (N étant la taille totale du tableau de nombres) et que je reprend votre code, avec du 2x2 (plus rapide à calculer, suffisant pour démontrer le problème), et que je donne une valeur à chaque combinaison possible sortant d'un new RandomIntMatrix / shuffle, j'obtiens la répartition suivante


    On vois clairement un grand écart (10%) entre la probabilité de certaines combinaisons et la probabilité d'autres, avec un noman's land entre les deux.

    Si je mélange N fois et non pas N/2 on s'améliore la répartition mais on perd en performances.



    Il nous reste 2.4% d'écart dans la répartitions des valeurs possibles. Alors combien de fois mélanger faut-il pour avoir du hasard acceptable pour vous?

    si N peut prendre de (très) grandes valeurs, il faut éviter toute idée faisant intervenir une deuxième structure contenant N^2 élément pour retenir les nombres déjà utilisés…
    mais si N est petit c'est sans doute moins important… (sauf si on fait çà des millions de fois dans le même programme…)
    et que l'idée de remplir le tableau avec les valeurs possibles et de le mélanger est plus censé que de dépendre de la "qualité" du générateur aléatoire… (le "tant que Random() ne renvoie pas un nombre non utilisé" a une durée d'exécution non déterministe…)
    Comme dit, tout est une question de ration nombres d'éléments à tire / taille de l'espace de nombres. Maintenant, si on se concentre sur le cas limité que vous présentez (il faut tirer tout l'espace), on ne fait au final que générer un ordre aléatoire, c'est ça le tirage. On peux alors les réaliser avec ce simpe algorithme (reprenant votre code)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public void shuffle() {
            int s2 = this.size * this.size ;
            for (int i = 0; i< s2; i++) // on crée un tableau triée
                this.content[i] = i+1;
            Random r = new Random();
            for (int i = 0; i< s2; i++){ // on tire au hasard chaque valeur dans la liste des valeur possible restantes
                int index = r.nextInt(s2-i);
                int tmp = this.content[i];
                // swap current position with a random number from residual list
                this.content[i]=this.content[i+index];
                this.content[i+index] = tmp;
            }
     
        }
    C'est le principe du tirage de carte, simplement pour ce cas particulier on a pas besoin de tableau intermédiaire (on utilise la partie pas encore tirée du tableau comme stockage)
    Images attachées Images attachées   

  14. #14
    Expert confirmé
    Homme Profil pro
    Inscrit en
    Septembre 2006
    Messages
    2 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Septembre 2006
    Messages : 2 957
    Points : 4 386
    Points
    4 386
    Par défaut
    Je ne vois pas trop comment vous avez mesuré vos résultats…

    ci-dessous, la Moyenne et la Déviation Standard sont donc celles du nombre de fois chaque combinaison possible a été générée par l'un et l'autre shuffle…

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
     
    Testing Matrix 2 x 2 on 1000000 shuffle runs
    Shuffle with 2 nextInt
    Number of different results: 24 (on 24 possibilities)
    Mean: 41666.666666666664
    Stddev: 281.766993966449
    **********
    Shuffle with 1 nextInt
    Number of different results: 24 (on 24 possibilities)
    Mean: 41666.666666666664
    Stddev: 1327.9184734848077
    -------------
    Testing Matrix 3 x 3 on 1000000 shuffle runs
    Shuffle with 2 nextInt
    Number of different results: 337859 (on 362880 possibilities)
    Mean: 2.9598145972136307
    Stddev: 1.5959995848065984
    **********
    Shuffle with 1 nextInt
    Number of different results: 339691 (on 362880 possibilities)
    Mean: 2.943851912473395
    Stddev: 1.5457611919130985
    au-delà de 3x3 cela devient trop lourd à calculer…
    (4x4 c'est 20922789888000 combinaisons…)

  15. #15
    Membre régulier
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    54
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Avril 2010
    Messages : 54
    Points : 74
    Points
    74
    Par défaut
    j'ai simplement mis sur graphe les données sorties, on vois clairement qu'il y a deux groupes données, ce qui est normal, en ne faisant que N/2 opérations de rotation, on peux facilement montrer que dans la moitié des cas, seul la moitié des éléments de la matrice on subit on opération de changement. On a donc une forte tendance à conserver des éléments qui se suivent. Bref, je n'ai pas besoin de sortir la calculette pour voir que du mélange au hasard, ce n'est pas si évident que vous voudriez le croire

  16. #16
    Expert confirmé
    Homme Profil pro
    Inscrit en
    Septembre 2006
    Messages
    2 957
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Septembre 2006
    Messages : 2 957
    Points : 4 386
    Points
    4 386
    Par défaut
    Citation Envoyé par CastorJoyeux Voir le message
    j'ai simplement mis sur graphe les données sorties, on vois clairement qu'il y a deux groupes données, ce qui est normal, en ne faisant que N/2 opérations de rotation, on peux facilement montrer que dans la moitié des cas, seul la moitié des éléments de la matrice on subit on opération de changement. On a donc une forte tendance à conserver des éléments qui se suivent. Bref, je n'ai pas besoin de sortir la calculette pour voir que du mélange au hasard, ce n'est pas si évident que vous voudriez le croire
    de fait N/2 n'était pas une bonne idée… ce n'était pas la bonne façon de limiter le nombre de nextInt() à size^2.

    et je n'ai pas prétendu que mélanger au hasard est trivial si l'on veut respecter des critères stricts et démontrables de qualité,
    (d'ailleurs votre solution a une moins bonne stddev pour N=2… que celle avec 2 nextInt() et travaillant sur N… mais pour N≥3 c'est idem…), j'ai seulement dit qu'il est évident que pour des N importants il est mieux d'éviter d'avoir recours à des solutions qui consomment 2x la mémoire nécessaire et surtout quand la méthode de test est O(n) en elle-même (comme List…)…
    et on ne peut quand même pas prétendre non plus que d'avoir un shuffle() raisonnablement bon soit si compliqué que çà…

Discussions similaires

  1. Réponses: 2
    Dernier message: 25/02/2014, 14h38
  2. [Débutant] comment remplir un tableau sous excel avec des données de DGV?
    Par spring.time dans le forum VB.NET
    Réponses: 6
    Dernier message: 26/10/2012, 20h36
  3. Réponses: 1
    Dernier message: 13/04/2011, 09h44
  4. [C#] Comment remplir un tableau avec un arraylist
    Par Cazaux-Moutou-Philippe dans le forum Windows Forms
    Réponses: 9
    Dernier message: 22/06/2006, 15h14
  5. [TChart] comment remplir un histogramme avec du rouge strié.
    Par :GREG: dans le forum Composants VCL
    Réponses: 2
    Dernier message: 12/08/2002, 09h37

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo