Permutations aléatoires

Télécharger le projet
Commenter

Description

Bonjour,

Une permutation aléatoire (en: random permutation, de: zufällige Permutation) de taille N, est une permutation prise de manière uniforme parmi l'ensemble des N! permutations possibles.

Le mélange de Fisher–Yates, également appelé mélange de Knuth (en: Knuth shuffles), est un bon algorithme dont le temps d'exécution augmente linéairement avec N.

Voici deux fonctions équivalentes basées sur template, dont la seconde (même nom sans '_'), concentrée sur une ligne, utilise quelques spécificités du langage C: 
template <typename TN>
void Rand_Permutation(TN *typ, int n) { // typ[] contient déjà une permutation
  for (int i=n-1; i>=0; --i) {
    int r=rand()%(i+1);
    TN e=typ[r];
    typ[r]=typ[i];
    typ[i]=e;
  }
}

template <typename TN>
void RandPermutation(TN *typ, int n) { // typ[] contient déjà une permutation
  for (int r, i=n; i>0;) {TN e=typ[r=rand()%i]; typ[r]=typ[--i]; typ[i]=e;}
}

Ces deux codes supposent que le tableau typ[] contient déjà une permutation de taille n.

Pour ceux qui aimeraient éviter d'utiliser template, une adaptation aux caractères char est donnée ci-après: 
void Rand_Permut(char *txt, int n) { // txt[] contient déjà une permutation
  for (int i=n-1; i>=0; --i) {
    int r=rand()%(i+1);
    char c=txt[r];
    txt[r]=txt[i];
    txt[i]=c;
  }
}

void RandPermut(char *txt, int n) { // txt[] contient déjà une permutation
  for (int r, i=n; i>0;) {char c=txt[r=rand()%i]; txt[r]=txt[--i]; txt[i]=c;}
}


Et voici une adaptation aux entiers int: 
void Rand_Permut(int *ent, int n) { // ent[] contient déjà une permutation
  for (int i=n-1; i>=0; --i) {
    int r=rand()%(i+1);
    int e=ent[r];
    ent[r]=ent[i];
    ent[i]=e;
  }
}

void RandPermut(int *ent, int n) { // ent[] contient déjà une permutation
  for (int r, i=n; i>0;) {int e=ent[r=rand()%i]; ent[r]=ent[--i]; ent[i]=e;}
}
Comme mentionné plus haut, tous ces codes supposent que le tableau donné en paramètre contient déjà une permutation, c'est-à-dire qu'il doit être préalablement initialisé.

Lorsqu'on travaille avec des ensembles d'entiers, il est possible de combiner la recherche d'une permutation aléatoire avec son initialisation.
Voir par exemple Wiki: Random permutation, sous Knuth shuffles. 
void Rand_Permut_Init(int *ent, int n) { // ent[]: assez grand non initialisé
  for (int i=0; i<n; i++) {
    int r=rand()%(i+1);
    ent[i]=ent[r];
    ent[r]=i;
  }
}

void RandPermutInit(int *ent, int n) { // ent[]: assez grand non initialisé
  for (int r, i=0; i<n; ++i) {ent[i]=ent[r=rand()%(i+1)]; ent[r]=i;}
}
L'initialisation implicite correspond ici à ent[]={0,1,2,3,...,n-1};


Le Zip contient le seul fichier source RandomPermutation.cpp qui, basé sur des ensembles de N=10 éléments, permet de tester le bon fonctionnement des routines présentées en affichant les M=6 premières permutations.

Répartition des éléments permutés
En appelant K=100000 fois les fonctions RandPermutation (avec deux types d'initialisation) et RandomPermutInit, on constate que, selon leur position, la répartition des éléments permutés est "uniforme" à 2% près.

Output généré par RandomPermutation.cpp: 
Rand_Permutation (template)
 JDACEHFGIB
 AEIDJHGBCF
 DAFJCEHIGB
 IEBFGJCDAH
 AIFBEJHCGD
 CBAIJDEGFH

RandPermutation (template)
 EDIFHABJCG
 DBFJIEHCAG
 GBDCIAHEFJ
 GBAHIFJCDE
 EJIBFAGHCD
 CDFJGAHEIB

Rand_Permut
 AEHDIFCBJG
 IBCGJEDFHA
 ADGJEFIBCH
 BEIAFGDJHC
 BIHEDCGJFA
 EHDFJAIGCB

RandPermut
 GJCHDIEFAB
 JEDCBFGAHI
 BGFDEIAHCJ
 AHFGCIDJBE
 BIGFAHECJD
 HEDACGBFJI

Rand_Permut
 7 0 4 3 1 2 9 6 5 8
 5 4 3 9 1 8 7 0 6 2
 7 1 8 6 3 5 2 4 0 9
 3 6 9 8 2 5 1 4 0 7
 4 8 7 2 5 6 3 9 0 1
 5 3 0 9 2 4 6 1 7 8

RandPermut
 4 3 1 2 7 5 9 8 0 6
 0 2 7 4 3 9 1 8 6 5
 7 8 3 5 0 1 6 2 4 9
 6 3 4 5 9 0 2 7 1 8
 4 7 2 6 9 0 5 8 1 3
 7 5 2 0 4 8 3 6 9 1

Rand_Permut_Init
 8 2 3 0 9 5 1 7 6 4
 1 6 2 5 3 0 7 4 9 8
 2 5 4 6 9 1 7 3 8 0
 2 7 5 8 6 1 3 9 4 0
 7 6 4 1 2 5 0 9 8 3
 0 9 8 4 7 6 1 5 2 3

RandPermutInit
 4 6 1 0 2 8 9 3 5 7
 3 8 7 9 6 2 1 5 0 4
 6 0 2 3 9 1 7 4 5 8
 0 1 7 9 6 2 5 8 3 4
 6 8 0 1 5 4 9 7 2 3
 8 4 1 6 2 5 7 3 0 9


=== Repartition des elements permutes selon leur position ===

100000 x RandPermutation, avec une seule initialisation:
          A     B     C     D     E     F     G     H     I     J
pos=0:  10003 10085  9946 10018 10050 10098  9895 10002  9905  9998
pos=1:   9987  9999 10158 10063  9987  9868 10233  9873  9911  9921
pos=2:  10030 10211  9985  9927  9962  9903  9977 10042  9949 10014
pos=3:  10058  9978  9793 10113 10161  9872  9942 10004  9902 10177
pos=4:   9842  9982 10121 10010 10059 10010 10056 10043  9977  9900
pos=5:  10037  9849 10002  9987 10017 10118  9940 10029  9989 10032
pos=6:   9924  9903  9959  9828  9906  9982 10015 10155 10100 10228
pos=7:  10088 10005 10079  9988  9830  9995 10007 10016 10022  9970
pos=8:  10057  9975  9938 10166 10090  9952  9982  9874 10012  9954
pos=9:   9974 10013 10019  9900  9938 10202  9953  9962 10233  9806

100000 x RandPermutation, avec une initialisation avant chaque appel:
          A     B     C     D     E     F     G     H     I     J
pos=0:  10028  9980 10037 10086 10052 10036  9821  9973 10057  9930
pos=1:   9926  9957 10057 10093  9936 10019 10219  9910  9911  9972
pos=2:   9950  9913 10040 10072 10103  9936 10040  9972 10120  9854
pos=3:   9796 10170 10184  9943  9768 10073 10001 10103 10002  9960
pos=4:  10048  9957 10030  9953 10071  9997  9891 10020 10179  9854
pos=5:  10034 10013 10031  9829  9944 10159 10115  9947  9882 10046
pos=6:   9974 10014  9871 10183  9989  9898  9941  9937 10000 10193
pos=7:  10033  9925 10045 10124 10019  9923 10011 10055  9964  9901
pos=8:  10219  9953  9976  9906  9858 10034 10001  9970  9897 10186
pos=9:   9992 10118  9729  9811 10260  9925  9960 10113  9988 10104

100000 x RandPermutInit, sans initialisation explicite:
          0     1     2     3     4     5     6     7     8     9
pos=0:  10169  9927  9975  9977 10034 10075 10041  9979  9821 10002
pos=1:  10001 10107  9972 10060  9947  9969 10030  9970  9983  9961
pos=2:   9985  9771  9973  9975  9991 10163 10121  9845 10161 10015
pos=3:   9857  9936 10072 10034 10053  9967  9998  9892 10162 10029
pos=4:   9992  9991 10000  9900 10115 10022 10086  9957  9989  9948
pos=5:   9921 10018 10051  9941  9856  9968  9988 10112 10106 10039
pos=6:  10010  9929  9885 10103 10054 10065  9882 10093 10062  9917
pos=7:   9983 10109 10215 10014  9932  9882  9997  9986  9776 10106
pos=8:  10032 10165  9934 10008 10075  9936  9791 10134  9979  9946
pos=9:  10050 10047  9923  9988  9943  9953 10066 10032  9961 10037


Autres liens intéressants:
CodeS-SourceS: Permutation aléatoire.
WikipédiA: Permutation aléatoire, Zufällige Permutation.
 
 
Bonne lecture ...
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)