permutations

Publié le par jö

Les permutations présentées ici sont considérées avec répétitions. On peut avoir besoin de générer des permutations contrôlées c'est-à-dire qu'après avoir généré n permutations successives, on est sûr d'avoir balayé les n permutations possibles à partir de la configuration initiale. Par exemple, dans l'article sur la distinction, pour savoir de combien de manières on peut enlever 2 billes à {3,2,1}, il faut générer (2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1) et (0,1,1) (c'est-à-dire les permutations contrôlées de (2,0,0) et (1,1,0) ), réaliser les différences (1,2,1),(3,0,1),(3,2,-1),(2,1,1),(2,2,0) et (3,1,0) avec {3,2,1}, et enfin supprimer celles qui sont non-conformes.

On va supposer que les indices débutent à 0 (comme pour le langage C) et que la configuration initiale, nécessaire à la génération des permutations et stockée dans le tableau t, est ordonnée c'est-à-dire que si on part de dhfidhhd, il conviendra de trouver un code qui assure que d<h<f<i (par exemple d=1,h=2,f=3,i=4) et d'utiliser la présentation qui donne
i pour l'indice 0,
f pour l'indice 1,
h pour les indices 2,3,4 et
d pour les indices 5,6,7

dans t.

On pose s=8 : on obtient les nb=s!/Prod(o!)=8!/(3!3!)=1120 permutations en utilisant un ensemble de n=4 compteurs c_i faisant le bilan des multiplicités m de d,h,f et i dans cet ordre. Pour être clair, c_0=d,c_1=h,c_2=f et c_3=i.

Une sous-fonction retrouve le compteur c_i  associé à une case j du tableau t:
int trad(j){ i=0; while(i<n&&c_i!=t[j])i++;}

2 sous-fonctions gèrent entrée et sortie :
void vide(i){k=trad(i);t[i]=-1;m(c_k)++;} // pour mettre la i-valeur de t dans le stock
void remplit(dest,source){t[dest]=c_source;m(c_source)--;}

1 sous-founction cherche le plus grand le plus proche de i dans c
int majorant(i){k=trad(i);j=n;do j--;while(j>=0&&(m(c_j)<=0||c_k>=c_j));}

1 sous-fonction cherche le plus petit absolu
int minorant(){k=n-1;while(k>=0&&m(c_k)<=0)k--;}

On peut alors remplir le tableau p des permutations en faisant :

ok=1
nb=0
ajoute(t,p);
nb++
do{
    i=1
    do{
       vide(i-1)
       j=majorant(i)
       i++
    }while(j<0&&i<s)
    if(j>=0&&i>1){
       i--
       vide(i)
       remplit(i,j)
       for(k=i-1;k>=0;k--)
          remplit(k,minorant())
       ajoute(t,p)
       nb++
    }else ok=0
}while(ok)

Publié dans mathblog

Commenter cet article