Discussion :

[cjacquel]

Bonjour,

J'ai un tableau ordonné:
0, 1, 2, 3, 4, 5

Comment générer le plus rapidement un tableau de ces chiffres mis aléatoirement :
4 3 5 2 0 1

Merci,
Christophe,

[Invité]

Bonjour, je pense qu'il te suffit de permuter deux éléments choisi aléatoirement "nombre d'élément du tableau"/2 fois.


Donc il faut tirer deux entiers appartenant à l'index du tableau et permuter les éléments aux deux index aléatoire max_element/2 fois

[tbc92]

Pour n éléments, faire n/2 permutations permet de bien mélanger, mais ce n'est pas aussi efficace qu'un tri aléatoire 'complet'.
Par exemple, à partir de 123456, un tri purement aléatoire peut donner 234561. Alors que faire 3 permutations ne peut pas donner ce résultat.
A priori, le plus économique, c'est de prendre 1 élément aléatoire, et le mettre en début de liste.
Et répéter l'opération n-1 fois. (n-1 en tout, ou, ne soyons pas radin, n fois en tout )
Après, selon le langage utilisé, selon je ne sais quel autre critère, selon la façon dont les données sont déplaçables dans une liste, il y a des variantes qui seront un peu plus rapides, ou un peu moins rapides.

[plaxtor]

Salut! Pour apporter un complément mathématique si tu veux que toutes tes permutations soient équiprobables tu ne peux pas appliquer la méthode de tbc92 je m'explique:
Si tu mélange de cette manière tu auras n^n issues équiprobables. Or le nombre de permutations (n!) ne divise pas n^n pour n>2 (car n-1 ne divise pas n) autrement dit toutes les permutations n'auront pas la même probabilité, ce n'est pas un 'bon' mélange donc. Si tu veux faire ça il faut que tu permutes le premier élément avec n'importe quel élément de la liste, le deuxième avec n'importe quel élément de la n-1 dernier termes (tous sauf le 1er donc) ... et l'avant dernier avec lui même ou dernier. Et là ça sera totalement aléatoire.

Mais je ne pense pas que ce soit la méthode la plus efficace, car le plus gourmand en temps, c'est de générer un nombre aléatoire. Personnellement je n'en génèrerai qu'un seul, dans [[0, n! - 1]] qui représenterait une permutation quelconque. Ensuite tu décompose ce nombre dans la base factorielle c'est à dire :

15 = 2*3! + 1*2! + 1*1! + 0*0! = (2,1,1,0)
155 = 1*5! + 1*4! + 1*3! + 2*2! + 1*1! + 0*0! (1,1,1,2,1,0)

Pour ton exemple tu fais n=6.
Mettons que tu tire 208 = 5! + 3*4! + 2*3! + 2*2! + 0*1! + 0*0! = (1,3,2,2,0)
Puis tu place les éléments dans ta liste :
au départ tu as liste = [0,1,2,3,4,5] et nouvelle_liste = []
Le premier chiffre est un 1
tu supprime l’élément d'indice 1 de ta liste (ici 1) et tu l'ajoute à nouvelle_liste :
liste = [0,2,3,4,5], nouvelle_liste = [1]
Le deuxième chiffre est un 3
tu supprime l’élément d'indice 3 de ta liste (ici 4) et tu l'ajoute à nouvelle_liste :
liste = [0,2,3,5], nouvelle_liste = [1,4]
...
liste = [], nouvelle_liste = [1,4,3,5,0,2]
Et voilà, c'est très facile à mettre en place et ça sert dans beaucoup de problèmes de dénombrement !

[tbc92]

@Plaxtor
J'aime BEAUCOUP cette idée de décomposition en base factorielle. Ca permet un parallèle direct entre le nombre de permutations n! et un identifiant entre 1 et n! .... Chaque permutation est associée à un nombre de façon unique. Ca a comme un coté pédagogique.

Quand j'ai besoin de trier une liste de façon aléatoire, en fait je fais exactement comme toi, mais sans passer par le calcul de n! :

Je prends un nombre aléatoire entre 1 et n, par exemple i. Je prends l'élément de rang i dans ma liste initiale, et je le mets en tête dans ma liste résultat. Et je le supprime de la liste initiale.
Et je répète l'opération n fois, en prenant à chaque étape E un nombre aléatoire entre 1 et N-E+1.

Ici, j'avais improvisé un algorithme pour trier une liste 'sur elle-même', sans passer par une deuxième liste.
... Mais après réflexion, c'est stupide, l'algorithme qu'on utilise toi ou moi peut parfaitement s'adapter au cas où on utilise une seule liste.

[plaxtor]

En effet, je pense que c'est le moyen le plus intuitif de créer une bijection entre l'ensemble des permutations entre (0,n) et l'ensemble des entiers (0, (n+1)! - 1)
Après comme j'ai dit cela dépend si tu t'autorises à générer un seul nombre aléatoire ou plusieurs. Avec un seul le mieux c'est ainsi, avec plusieurs la méthode que tu décris convient parfaitement (et si on veut faire sur place on permute au lieu de supprimer dans l'un et d'ajouter dans l'autre) !

[tbc92]

@plaxtor :
détail :

on ne permute pas, on prend un élément aléatoire on le retire de là où il est , et on le met en dernier (ou en premier, c'est un choix).
Et tous les éléments intermédiaires sont donc décalés d'un cran.

[plaxtor]

On peut faire les deux !!! Du moment que tu ne touches plus à l’élément que tu as déplacé ou permuté.

Soit comme tu dis on prends un des n éléments qu'on glisse en premier, puis un des n-1 derniers que l'on glisse en premier etc...
Soit on prend le premier on le permute avec un autre, puis le deuxième qu'on permute avec un autre (sauf le premier) etc...

Ce sont deux méthodes qui conduisent au même résultat ! La première est plus naturelle peut être, mais je trouve que la dernière méthode est légèrement plus simple à mettre en place, vu que l'on fait :liste[a], liste[b] = liste[b], liste[a] mais chacun son avis
Mais si tu fais n fois une opération avec à chaque fois n possibilités ça ne peut pas être équiprobable !

[tbc92]

J'ai des gros doutes.
Tu fais combien de permutations ?
Si tu fais n/2 permutations, tu ne couvres pas toutes les possibilités : à partir de 123456, on ne peut pas arriver à 234561 en 3 permutations
Quand tu permutes a et b, ou bien b et a, tu arrives au même résultat. Donc avec n/2 permutations, tu arrives à n! / puissance( 2, n/2) combinaisons.

Avec des permutations, il y a ce facteur 2 qui vient perturber les résultats.

[plaxtor]

Ah j'ai mal du m'exprimer ! J'en fait n exactement, regarde :
[0,1,2,3,4,5,6] on choisit 3
[3,1,2,0,4,5,6] on choisit 4
[3,4,2,0,1,5,6] on choisit 6
[3,4,6,0,1,5,2] on choisit 5
[3,4,6,5,1,0,2] on choisit 2
[3,4,6,5,2,0,1] on choisit 0
[3,4,6,5,2,0,1] on choisit 1 (la on a pas trop le choix hein )
C'est facile de voir que P(k soit en indice 0) = 1/n
Puis par récurrence sur la liste extraite (en retirant le premier indice) que P(k soit en indice i) = 1/n
Ta méthode et la mienne reviennent strictement au même !!

[kolodz]

Bonjour,

Beaucoup de langage propose avec leur API une fonction correspondante. Je te joins ici le code correspondant de l'implémentation Java :
Classe source : java.util.Collections.java

Code java :

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
    private static final int SHUFFLE_THRESHOLD        =    5;
 
    /**
     * Randomly permutes the specified list using a default source of
     * randomness.  All permutations occur with approximately equal
     * likelihood.
     *
     * <p>The hedge "approximately" is used in the foregoing description because
     * default source of randomness is only approximately an unbiased source
     * of independently chosen bits. If it were a perfect source of randomly
     * chosen bits, then the algorithm would choose permutations with perfect
     * uniformity.
     *
     * <p>This implementation traverses the list backwards, from the last
     * element up to the second, repeatedly swapping a randomly selected element
     * into the "current position".  Elements are randomly selected from the
     * portion of the list that runs from the first element to the current
     * position, inclusive.
     *
     * <p>This method runs in linear time.  If the specified list does not
     * implement the {@link RandomAccess} interface and is large, this
     * implementation dumps the specified list into an array before shuffling
     * it, and dumps the shuffled array back into the list.  This avoids the
     * quadratic behavior that would result from shuffling a "sequential
     * access" list in place.
     *
     * @param  list the list to be shuffled.
     * @throws UnsupportedOperationException if the specified list or
     *         its list-iterator does not support the <tt>set</tt> operation.
     */
    public static void shuffle(List<?> list) {
        Random rnd = r;
        if (rnd == null)
            r = rnd = new Random(); // harmless race.
        shuffle(list, rnd);
    }
 
    private static Random r;
 
    /**
     * Randomly permute the specified list using the specified source of
     * randomness.  All permutations occur with equal likelihood
     * assuming that the source of randomness is fair.<p>
     *
     * This implementation traverses the list backwards, from the last element
     * up to the second, repeatedly swapping a randomly selected element into
     * the "current position".  Elements are randomly selected from the
     * portion of the list that runs from the first element to the current
     * position, inclusive.<p>
     *
     * This method runs in linear time.  If the specified list does not
     * implement the {@link RandomAccess} interface and is large, this
     * implementation dumps the specified list into an array before shuffling
     * it, and dumps the shuffled array back into the list.  This avoids the
     * quadratic behavior that would result from shuffling a "sequential
     * access" list in place.
     *
     * @param  list the list to be shuffled.
     * @param  rnd the source of randomness to use to shuffle the list.
     * @throws UnsupportedOperationException if the specified list or its
     *         list-iterator does not support the <tt>set</tt> operation.
     */
    @SuppressWarnings({"rawtypes", "unchecked"})
    public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();
 
            // Shuffle array
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));
 
            // Dump array back into list
            // instead of using a raw type here, it's possible to capture
            // the wildcard but it will require a call to a supplementary
            // private method
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }
 
    /**
     * Swaps the two specified elements in the specified array.
     */
    private static void swap(Object[] arr, int i, int j) {
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

Je suppose que si tu cherche tu peux trouver la version utilisé pour dans l'API du langage que tu cible.

Cordialement,
Patrick Kolodziejczyk.

[Flodelarab]

Bonjour,

Soit une liste triée A,B,C,D,E,F.
Tirons un nombre i1 entre 0 et 5.
Tirons un nombre i2 entre 0 et 4.
Tirons un nombre i3 entre 0 et 3.
...
Tirons un nombre i5 entre 0 et 1.

Ces nombres i sont les indices des places de A,B,C,D,E, et F dans le nouveau tableau en fonction des places restantes. La lettre F n'a pas de nombre aléatoire car elle se place naturellement dans la dernière place libre.

Mon idée de départ était de tirer une bonne fois pour toute un nombre en base 6 pour placer les lettres. Mais il ne faut pas de redondance et la base est donc décroissante.